sport

Cei $N$ elevi din Colegiul Național „I. L. Caragiale” Ploiești intră pe rând în sala de sport, în ordinea $1, 2, \ldots, N$. Înălțimile celor $N$ elevi sunt cunoscute și sunt notate cu $H_1, H_2, \ldots, H_N$.

Profesorul de sport îi așază în linie, în ordinea în care intră. Pentru fiecare elev care intră în sala de sport, profesorul poate să aleagă să îl așeze la începutul liniei sau la sfârșitul liniei, cu scopul ca la final elevii să fie ordonați crescător după înălțime. Dacă profesorul nu are posibilitatea de a așeza elevii în această ordine, acesta s-ar supăra, așa că elevii trebuie să se asigure că vor intra în sală într-un mod corespunzător.

Elevii pot să se rearanjeze între ei înainte de a intra în sală, dar nu pot să se rearanjeze după ce au intrat în sală. Pentru aceasta, ei pot face operații de mutare.

Printr-o operație de mutare, un elev este mutat din poziția în care se află într-o altă poziție în șirul de elevi de la intrarea în sala de sport.

Cerință

Scrieți un program care cunoscând numărul de elevi $N$, precum și înălțimile acestora, determină numărul minim de operații de mutare necesare pentru a rearanja elevii, astfel încât, la intrarea lor în sala de sport, profesorul să poată așeza elevii în ordinea crescătoare a înălțimilor?

Date de intrare

Fișierul de intrare sport.in conține numărul natural $N$ pe prima linie, iar pe a doua linie conține $N$ numere naturale $H_1, H_2, \ldots, H_N$, separate prin spații.

Date de ieșire

Fișierul de ieșire sport.out conține o singură linie pe care este scris numărul minim de operații de mutare necesare pentru a rearanja elevii conform condițiilor din enunț.

Restricții și precizări

• $1 \leq N \leq 250 \ 000$;
• $1 \leq H_i \leq 10^9$ pentru $1 \leq i \leq N$;
• Pentru teste valorând $75$ de puncte, înălțimile elevilor sunt distincte.

Exemplul 1

sport.in

5
3 4 2 5 1

sport.out

0

Explicație

Elevul cu înălțimea $3$ intră primul în sală, elevul cu înălțimea $4$ intră la sfârșitul liniei, elevul cu înălțimea $2$ intră la începutul liniei, elevul cu înălțimea $5$ intră la sfârșitul liniei, iar elevul cu înălțimea $1$ intră la începutul liniei. Astfel, elevii sunt așezați în ordine crescătoare, deci nu sunt necesare operații de mutare suplimentare.

Exemplul 2

sport.in

5
10 8 8 9 12

sport.out

1

Explicație

Este necesară o operație de mutare. O operație posibilă este ca elevul cu înălțimea $9$ trebuie mutat după elevul cu înălțimea $10$.