Voller Ehrgeiz möchte Farmer John etwas versuchen, das nie ganz gelingt: seine gesamte Kuhherde fotografieren.

Für ein schönes Foto sollen die Kühe von der kleinsten bis zur größten in einer Reihe stehen. Leider verlässt die stets störende Bessie unmittelbar danach die Reihe und stellt sich an einer anderen Stelle wieder hinein!

Farmer John möchte Kuhpaare vertauschen, damit die gesamte Herde wieder richtig geordnet ist. Bestimme die Mindestzahl benötigter Vertauschungen.

Eingabe

Die erste Eingabezeile enthält $N$ ($2 \leq N \leq 100$). Die nächsten $N$ Zeilen beschreiben die Körperhöhen in der Reihenfolge nach Bessies Bewegung. Jede Höhe ist eine ganze Zahl im Bereich $1 \ldots 1,000,000$. Kühe können dieselbe Höhe haben.

Ausgabe

Gib die Mindestzahl von Vertauschungen zwischen Kuhpaaren für die richtige Reihenfolge aus. Die vertauschten Kühe müssen nicht benachbart sein.

Beispiele

Eingabe 1

6
2
4
7
7
9
3

Ausgabe 1

3

Hinweis

Hier ist Bessie offensichtlich die Kuh mit Höhe 3. FJ stellt die Ordnung mit den folgenden drei Vertauschungen wieder her:

2 4 7 7 9 3 - Ursprüngliche Reihe
2 4 7 7 3 9 - Die letzten zwei Kühe vertauschen
2 4 3 7 7 9 - Die erste 7 und die 3 vertauschen
2 3 4 7 7 9 - Die 4 und die 3 vertauschen

Aufgabenautor: Brian Dean