AlanashKO liebt Geld. Am Vorabend des Neujahrsfests bekam er $N$ Banknoten. Der Nennwert jeder Banknote ist eine positive ganze Zahl. Beim Spielen legte AlanashKO alle Banknoten in eine Reihe und nummerierte sie von links nach rechts von $1$ bis $N$. Dann beschloss er, alle Banknoten in nicht absteigender Reihenfolge zu sortieren. Dazu führt AlanashKO folgendes Verfahren aus: Zuerst teilt er die Banknoten in ein oder mehrere disjunkte Teilsegmente auf, wobei jede Banknote zu einem Teilsegment gehört. Anschließend werden alle Teilsegmente der Reihe nach von links nach rechts in eine neue Reihe eingefügt: zuerst das am weitesten links liegende Teilsegment (das erste Teilsegment), dann das nächste von links und so weiter. Jedes Teilsegment wird entweder zwischen zwei beliebigen Banknoten oder an einem der beiden Enden der aktuellen neuen Reihe eingefügt. Die Reihenfolge der Banknoten innerhalb eines Teilsegments bleibt beim Einfügen unverändert.

AlanashKO möchte die Anzahl der Teilsegmente minimieren, mit denen er die Banknoten schließlich in nicht absteigender Reihenfolge sortieren kann. Hilf ihm, diesen Wert zu finden.

Eingabe

Die erste Zeile enthält eine positive ganze Zahl $N$ ($1 \le N \le 10^6$) — die Anzahl der Banknoten. Die nächste Zeile enthält $N$ positive ganze Zahlen $a_i$ ($1 \le a_i \le 10^6$) — den Wert der $i$-ten Banknote.

Ausgabe

Gib in einer einzigen Zeile eine ganze Zahl aus — die minimale Anzahl von Teilsegmenten, mit denen AlanashKO die Banknoten sortieren kann.

Teilaufgaben

Diese Aufgabe umfasst vier Teilaufgaben:

1. $N \le 8$. 9 Punkte.
2. $N \le 20$. 16 Punkte.
3. $N \le 300$. 20 Punkte.
4. $N \le 10^6$. 55 Punkte.

Eine Teilaufgabe wird nur gewertet, wenn die Lösung alle vorherigen Teilaufgaben erfolgreich besteht.

Beispiele

Eingabe 1

6
3 6 4 5 1 2

Ausgabe 1

3

Hinweis

Ein Teilsegment ist eine zusammenhängende Folge.

Betrachten wir den Beispieltest:

Die minimale Antwort ergibt sich aus der Aufteilung in 3 Teilsegmente: |3 6|4 5|1 2| (die Striche markieren die Grenzen der Teilsegmente).

Nach dem ersten Schritt ist die ursprüngliche Reihe |4 5|1 2| und die neue Reihe |3 6|.

Im zweiten Schritt wird das Teilsegment |4 5| zwischen $3$ und $6$ eingefügt.

Nach dem zweiten Schritt ist die ursprüngliche Reihe |1 2| und die neue Reihe |3 4 5 6|.

Dann wird das Teilsegment |1 2| am Anfang der neuen Reihe eingefügt, sodass sich |1 2 3 4 5 6| ergibt.