Problem 94: QSwap

După ce te-ai jucat cu IP-urile de Neuralink, ai căpătat o pasiune pentru permutări. Ai reușit să faci rost de o permutare p de lungime N și ți-ai propus un obiectiv simplu: să o sortezi efectuând un număr minim de swapuri (interschimbări) între elemente adiacente. Prietenul tău Radu Slav a observat noua ta preocupare, și pentru a te ajuta să nu pierzi prea mult timp sortând permutarea, s-a oferit să te ajute: el îți oferă o extra operație swap specială, pe care o poți folosi la orice moment sau o poți ignora, dar care poate fi efectuată între oricare 2 elemente din p (nu neapărat adiacente). Acum, vrei să calculezi numărul total minim de operații, având în vedere că poți folosi de oricâte ori operația $swap(i, i + 1)$ , 1 ≤ i < N și maxim o dată operația oferită de Radu, $swap(i, j)$ , 1 ≤ i < j ≤ N, unde rezultatul operației $swap(x, y)$ aplicate asupra permutării $p = p_1, p_2, ... , p_x, ... , p_y, ..., p_N$ este $p' = p_1, p_2, ... , p_y, ... , p_x, ..., p_N$ .

Date de intrare

Pe prima linie se găsește un număr întreg N, reprezentând lungimea permutării.
Pe cea de-a doua linie se găsesc N numere întregi $p_1 ... p_N$ , reprezentând permutarea ce trebuie sortată

Date de ieșire

Se va afișa o singură linie, ce conține un singur număr întreg, reprezentând numărul minim de operații necesare pentru a sorta permutarea.

Restricții și precizări

1 ≤ N ≤ 1 000 000
p este o permutare validă numerelor de la 1 la N

Subtask 1 (7 puncte)

1 ≤ N ≤ 10

Subtask 2 (8 puncte)

1 ≤ N ≤ 100

Subtask 3 (9 puncte)

1 ≤ N ≤ 500

Subtask 4 (10 puncte)

1 ≤ N ≤ 2 500

Subtask 5 (11 puncte)

1 ≤ N ≤ 10 000

Subtask 6 (16 puncte)

1 ≤ N ≤ 100 000
Permutarea este generată aleator uniform din mulțimea permutărilor de lungime N

Subtask 7 (27 puncte)

1 ≤ N ≤ 250 000

Subtask 8 (12 puncte)

Fără restricții suplimentare.

Exemplu

stdin

5
4 2 1 5 3

stdout