Farmer John will seine ganze Herde $N$, $1 \le N \le 100,000$, Nummern $1..N$, fotografieren, um Freunden zu imponieren.

Am Fototag laufen die Kühe und bilden eine beliebige Reihe, Position $i$ mit $c_{i}$, $1 \le c_{i} \le N$. Er hat eigene Ordnungsideen.

FJ meint: Kuh $i$ darf nur links von $i+1$ stehen für alle $i$, $1 \le i \le N-1$, und $N$ nur links von $1$. Natürlich steht niemand links der ersten, äußersten linken Kuh.

Hungrig warten sie aufs versprochene Essen nach dem Foto. Er will schnell fertig sein. Anweisungen folgen sie schlecht: Ein Nachbarpaar darf einmal je Minute tauschen. Wie schnell entsteht eine akzeptable Ordnung?

Fünf Kühe anfangs:

     Links           Rechts
        3  5  4  2  1

Erst das zweite Paar tauschen:

        3  4  5  2 1

Dann das äußerste rechte:

        3  4  5  1  2

Eine passende Ordnung in nur zwei Tauschminuten.

Eingabe

• Zeile $1$: eine ganze Zahl $N$.

• Zeilen $2..N+1$: Zeile $i+1$, Nummer $c_{i}$ der $i$-ten Kuh.

Ausgabe

• Zeile $1$: minimale Zeit in Minuten zur passenden Ordnung.

Beispiele

Eingabe 1

5
3
5
4
2
1

Ausgabe 1

2

Hinweis

Aufgabenautor: Travis, 2010