Es gibt einen kreisförmigen Parkturm mit $N$ im Kreis angeordneten Fächern. Sie heißen im Uhrzeigersinn Fach 1, Fach 2, ..., Fach $N$. Jedes Fach enthält ein Auto. Das Auto in Fach $i$ hat die Nummer $a_i$.

Der Turm hat zwei Knöpfe. A dreht ihn um ein Fach im Uhrzeigersinn, B um ein Fach gegen den Uhrzeigersinn. Die linke Abbildung unten zeigt das obige Beispiel nach Drücken von A, die rechte nach Drücken von B.

Alle Autos sollen aus dem Turm entfernt werden.

Autos können nur aus dem einen Fach ganz unten entfernt werden. Anfangs ist Fach 1 ganz unten. Um ein Auto aus einem anderen Fach zu entfernen, muss man zunächst durch geeignete Knopfdrücke sein Fach nach unten drehen.

Außerdem müssen vor dem Entfernen eines Autos mit Nummer $x$ alle Autos mit kleineren Nummern entfernt werden. Solange also ein Auto mit Nummer kleiner als $x$ im Turm verbleibt, darf kein Auto mit Nummer $x$ entfernt werden.

Schreibe ein Programm, das die kleinste Gesamtzahl von Knopfdrücken zum Entfernen aller Autos bestimmt.

Beschränkungen

• $1 \le N \le 100\,000$
• $1 \le a_i \le 1\,000\,000\,000$

Teilaufgaben

1. (8 Punkte) $a_i=1$ ($1\le i\le N$), also haben alle Autos die Nummer 1.
2. (9 Punkte) $a_i\ne a_j$ für $i\ne j$, also haben alle Autos verschiedene Nummern.
3. (10 Punkte) $N\le10$.
4. (21 Punkte) $N\le100$.
5. (31 Punkte) $N\le1\,000$.
6. (21 Punkte) Keine zusätzlichen Beschränkungen.

Eingabe

Die erste Zeile enthält eine ganze Zahl $N$.

Die zweite enthält die Autonummern $a_1,\ldots,a_N$ in ihrer Reihenfolge, durch Leerzeichen getrennt.

Ausgabe

Gib in der ersten Zeile die kleinste Gesamtzahl der Knopfdrücke aus.

Beispiele

Eingabe 1

4
1 2 2 1

Ausgabe 1

3

Hinweis

Man kann in dieser Reihenfolge vorgehen: Auto entfernen → Knopf A → Auto entfernen → Knopf A → Auto entfernen → Knopf A → Auto entfernen.

Eingabe 2

5
3 1 4 5 1

Ausgabe 2

7