Farmer John veut photographier tout son troupeau de $N$ vaches, $1 \le N \le 100,000$, numéros $1..N$, pour épater ses amis.

Le jour de la photo, elles courent pour former une ligne arbitraire, position $i$ occupée par $c_{i}$, $1 \le c_{i} \le N$. Il a ses idées d'ordre.

Selon FJ, La vache $i$ ne peut se tenir qu'à gauche de $i+1$ pour tout $i$, $1 \le i \le N-1$, et $N$ qu'à gauche de $1$. Bien sûr, personne à gauche de la première, la plus à gauche.

Affamées, elles attendent le dîner promis après la photo, et il veut aller vite. Elles suivent mal les consignes : une paire voisine peut être échangée une fois par minute. Quel délai pour un ordre acceptable ?

Exemple de cinq vaches initiales :

     Gauche           Droite
        3  5  4  2  1

Échangez d'abord la deuxième paire :

        3  4  5  2 1

Puis celle la plus à droite :

        3  4  5  1  2

Ordre acceptable en deux minutes seulement.

Entrée

• Ligne $1$ : un entier $N$.

• Lignes $2..N+1$ : ligne $i+1$, numéro $c_{i}$ de la vache $i$.

Sortie

• Ligne $1$ : temps minimal en minutes pour un ordre convenable.

Exemples

Entrée 1

5
3
5
4
2
1

Sortie 1

2

Remarque

Auteur du problème : Travis, 2010