Bartek ist ein bekannter Techno-Musikproduzent und perfektioniert derzeit seinen nächsten Hit. Er hat einen Track bestehend aus $n$ Beats erstellt, die fortlaufend von $1$ bis $n$ nummeriert sind. Nachdem er Stunden in einem Musikbearbeitungsprogramm verbracht hatte, wollte er gerade die mp3-Datei exportieren, bemerkte aber, dass die Beats aktuell in der Reihenfolge $a_1, a_2, \dots, a_n$ angeordnet sind. Bartek muss eine aufsteigende Reihenfolge der Beats erreichen, also $1, 2, \dots, n$.
Das Programm erlaubt zwei Arten von Operationen:
- Verschiebe den letzten Beat an eine beliebige Position, z. B. $(2, 4, 1, 5, \underline{3}) \to (2, \underline{3}, 4, 1, 5)$.
- Verschiebe einen beliebigen Beat an den Anfang, z. B. $(2, 4, 1, \underline{5}, 3) \to (\underline{5}, 2, 4, 1, 3)$.
Was ist die minimale Anzahl an Operationen, die benötigt wird, um die Beats in aufsteigender Reihenfolge anzuordnen?
Eingabe
Die erste Zeile enthält eine ganze Zahl $n$ ($1 \le n \le 200\,000$), welche die Anzahl der Beats bezeichnet.
Die zweite Zeile enthält $n$ paarweise verschiedene ganze Zahlen $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n; a_i \ne a_j$), welche die aktuelle Reihenfolge der Beats im Programm darstellen.
Ausgabe
Gib eine einzige ganze Zahl aus – die minimale Anzahl erforderlicher Operationen.
Beispiele
Eingabe 1
6 3 2 5 4 1 6
Ausgabe 1
4
Eingabe 2
9 3 1 2 5 6 4 9 7 8
Ausgabe 2
6
Hinweis
Wir beginnen mit der Beat-Folge $(3, 2, 5, 4, 1, 6)$. Hier ist eine Möglichkeit, die gewünschte Reihenfolge in vier Operationen zu erreichen:
- Verschiebe den letzten Beat um zwei Plätze nach links: $(3, 2, 5, \underline{6}, 4, 1)$.
- Verschiebe Beat $2$ an den Anfang: $(\underline{2}, 3, 5, 6, 4, 1)$.
- Verschiebe Beat $1$ an den Anfang: $(\underline{1}, 2, 3, 5, 6, 4)$.
- Verschiebe den letzten Beat um zwei Plätze nach links: $(1, 2, 3, \underline{4}, 5, 6)$.
Es ist möglich, eine aufsteigende Reihenfolge auch auf andere Weise mit vier Operationen zu erhalten, aber es ist nicht in drei Operationen machbar, sodass das Ergebnis $4$ lautet.