== include(page="template/taskheader" task_id="sport") ==
Poveste si cerinta...
La ora de sport, cei $N$ elevi din clasa s-au aliniat pe un singur rand in fata profesorului. Nu au incercat sa se ordoneze dupa inaltime, deoarece stiau ca profesorul are propria metoda de ordonare, pe care o aplica la inceputul fiecarei ore. Profesorul alege un elev, pe care-l trimite la unul dintre cele doua capete ale randului. Procedeul se repeta pana cand sirul de elevi este ordonat crescator dupa inaltime. Copiii s-au gandit sa-l ajute pe profesor sa-si perfectioneze metoda, astfel incat numarul de elevi care vor fi mutati prin acest procedeu la un capat sau la celalalt al sirului sa fie minim.
h2. Cerinta
Cunoscand numarul de elevi, inaltimile si pozitiile lor initiale in sir, determinati numarul minim de mutari pe care profesorul de sport trebuie sa le aplice, pentru a ordona sirul de elevi, crescator dupa inaltime.
h2. Date de intrare
Fisierul de intrare $sport.in$ ...
Fisierul de intrare $sport.in$ contine pe prima linie numarul natural $N$ reprezentand numarul de copii. Pe linia a doua, se gasesc $N$ numere naturale distincte: $A{~1~}$, $A{~2~}$, ... , $A{~N~}$ separate prin cate un singur spatiu. Al $i-lea$ numar de pe linie reprezinta inaltimea copilului care se afla pe pozitia $i$ inainte de orice operatie de mutare.
h2. Date de iesire
In fisierul de iesire $sport.out$ ...
In fisierul de iesire $sport.out$ se va scrie pe prima linie un numar natural $M$, reprezentand numarul minim de mutari pe care profesorul le poate face pentru a sorta sirul de elevi, crescator dupa inaltime.
h2. Restrictii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1.000$
* $1 ≤ A{~i~} ≤ 10.000$
h2. Exemplu
table(example). |_. sport.in |_. sport.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 4
2 1 3 5
| 1
|
| 3
3 2 1
| 2
|
| 5
3 7 2 6 9
| 3
|
h3. Explicatie
...
# Profesorul muta elevul de inaltime $1$ la capatul din stanga: $1 2 3 5$
# Profesorul are la dispozitie mai multe variante cu minimum $2$ mutari. Prezentam una dintre acestea:
** Muta elevul de inaltime $1$ la capatul din stanga: $1$ $3$ $2$
** Muta elevul de inaltime $3$ la capatul din dreapta: $1 2 3$
# Minimum 3 mutari. Una dintre variante este:
** Muta elevul de inaltime $7$ la capatul din dreapta: $3 2 6 9 7$
** Muta elevul de inaltime $2$ la capatul din stanga: $2 3 6 9 7$
** Muta elevul de inaltime $9$ la capatul din dreapta: $2 3 6 7 9$
== include(page="template/taskfooter" task_id="sport") ==
