sport

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$, $\dots$, $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 și precizări

• $1 < N \leq 1 \ 000$
• $1 \leq H_i \leq 10 \ 000$

Exemplul 1

sport.in

4
2 1 3 5 

sport.out

1

Explicație

Profesorul mută elevul de înălţime $1$ la capătul din stânga: $1 \ 2 \ 3 \ 5$

Exemplul 2

sport.in

3
3 2 1 

sport.out

2

Explicație

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$

Exemplul 3

sport.in

5
3 7 2 6 9

sport.out

3

Explicație

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$