Ambitieux, Farmer John veut tenter quelque chose qui ne semble jamais bien se passer : photographier tout son troupeau.

Pour une belle photo, il veut aligner les vaches de la plus petite à la plus grande. Malheureusement, juste après leur mise en place, Bessie, toujours perturbatrice, sort de la file et se réinsère ailleurs !

Farmer John veut échanger des paires de vaches pour remettre tout le troupeau dans le bon ordre. Aidez-le à déterminer le nombre minimal d’échanges nécessaires.

Entrée

La première ligne contient $N$ ($2 \leq N \leq 100$). Les $N$ lignes suivantes donnent les tailles des vaches dans l’ordre après le déplacement de Bessie. Chaque taille est un entier dans l’intervalle $1 \ldots 1,000,000$. Des vaches peuvent avoir la même taille.

Sortie

Affichez le nombre minimal d’échanges de paires de vaches nécessaires pour rétablir l’ordre. Les vaches échangées ne doivent pas nécessairement être voisines.

Exemples

Entrée 1

6
2
4
7
7
9
3

Sortie 1

3

Remarque

Ici, Bessie est clairement la vache de taille 3. FJ rétablit l’ordre avec les trois échanges ci-dessous :

2 4 7 7 9 3 - File initiale
2 4 7 7 3 9 - Échanger les deux dernières vaches
2 4 3 7 7 9 - Échanger le premier 7 et le 3
2 3 4 7 7 9 - Échanger le 4 et le 3

Auteur du problème : Brian Dean