Für ein ganzzahliges Feld $A$ der Größe $N$ ist die Mischoperation folgendermaßen definiert:

• Zunächst erstellen Sie ein leeres ganzzahliges Feld $B$.
• Solange $A$ nicht leer ist, entfernen Sie sein linkestes oder rechtestes Element und hängen dessen Wert rechts an $B$ an.
• Ist $A$ leer, ersetzen Sie $A$ durch $B$ und beenden die Operation.

Wird die Mischoperation wie in der obigen Abbildung ausgeführt, ändert sich das Feld $A$ wie folgt:

$$ (34,19,5,36,4,25,12,9)\to(9,34,19,12,25,4,5,36). $$

Sei $A_i$ das $i$-te Element von $A$. Gilt die Bedingung „Für $1 \le i<j \le N$ gilt $A_i \le A_j$“, so heißt das Feld $A$ monoton aufsteigend.

Schreiben Sie ein Programm, das für ein gegebenes ganzzahliges Feld $A$ der Größe $N$ die minimale Anzahl von Mischoperationen berechnet, um $A$ monoton aufsteigend zu machen.

Eingabe

Die erste Eingabezeile enthält eine ganze Zahl $N$, die Anzahl der Elemente von $A$ ($1 \le N \le 3\cdot10^5$).

Die zweite Zeile enthält $N$ ganze Zahlen $A_1,\ldots,A_N$, die Anfangswerte der Elemente von $A$ ($1 \le A_i \le 10^9$).

Ausgabe

Geben Sie die minimale Anzahl von Mischoperationen aus, um $A$ monoton aufsteigend zu machen.

Beispiele

Eingabe 1

3
2 2 5

Ausgabe 1

0

Eingabe 2

6
1 5 8 10 3 2

Ausgabe 2

1