La ora de sport, cei N elevi din clasă s-au aliniat pe un singur rând în faţa profesorului. Nu au încercat să se ordoneze după înălţime, deoarece ştiau că profesorul are propria metodă de ordonare, pe care o aplică la începutul fiecărei ore. Profesorul alege un elev, pe care-l trimite la unul dintre cele două capete ale rândului. Procedeul se repetă până când şirul de elevi este ordonat crescător după înălţime. Copiii s-au gândit să-l ajute pe profesor să-şi perfecţioneze metoda, astfel încât numărul de elevi care vor fi mutaţi prin acest procedeu la un capăt sau la celălalt al şirului să fie minim.
Cerinţă
Cunoscând numărul de elevi, înălţimile şi poziţiile lor iniţiale în şir, determinaţi numărul minim de mutări pe care profesorul de sport trebuie să le aplice, pentru a ordona şirul de elevi, crescător după înălţime.
Date de intrare
Fişierul de intrare sport.in conţine pe prima linie numărul natural N reprezentând numărul de copii. Pe linia a doua, se găsesc N numere naturale distincte: H[1], H[2], …, H[N], separate prin câte un singur spaţiu. Al i-lea număr de pe linie reprezintă înălţimea copilului care se află pe poziţia i înainte de orice operaţie de mutare.
Date de ieşire
În fişierul de ieşire sport.out se va scrie pe prima linie un număr natural M, reprezentând numărul minim de mutări pe care profesorul le poate face pentru a sorta şirul de elevi, crescător după înălţime.
Restricţii
1 < N ≤ 1000
1 ≤ H[i] ≤ 10000
Exemple
sport.in
sport.out
Explicaţii
4
2 1 3 5
1
Profesorul mută elevul de înălţime 1 la capătul din stânga: 1 2 3 5
3
3 2 1
2
Profesorul are la dispoziţie mai multe variante cu minimum 2 mutări. Prezentăm una dintre acestea:
Mută elevul de înălţime 1 la capătul din stânga: 1 3 2
Mută elevul de înălţime 3 la capătul din dreapta: 1 2 3
5
3 7 2 6 9
3
Minimum 3 mutări. Una dintre variante este:
Mută elevul de înălţime 7 la capătul din dreapta: 3 2 6 9 7
Mută elevul de înălţime 2 la capătul din stânga: 2 3 6 9 7
Mută elevul de înălţime 9 la capătul din dreapta: 2 3 6 7 9