Dla danej tablicy liczb całkowitych $A$ o rozmiarze $N$, operacja shuffle (tasowanie) jest zdefiniowana w następujący sposób:

• Początkowo tworzysz pustą tablicę liczb całkowitych $B$.
• Następnie, dopóki $A$ nie jest pusta, usuwasz albo najbardziej lewy, albo najbardziej prawy element $A$ i dopisujesz tę wartość na koniec $B$.
• Jeśli $A$ jest pusta, zastąp $A$ tablicą $B$ i zakończ.

Jeśli operacja shuffle zostanie wykonana tak, jak pokazano na powyższym rysunku, wartość tablicy $A$ zmieni się w następujący sposób:

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

Niech $A_i$ będzie $i$-tym elementem tablicy $A$. Mówimy, że tablica $A$ jest niemalejąca, jeśli spełniony jest warunek: „jeśli $1 \le i < j \le N$, to $A_i \le A_j$”.

Napisz program, który dla danej tablicy liczb całkowitych $A$ o rozmiarze $N$ obliczy minimalną liczbę operacji shuffle wymaganych do tego, aby tablica $A$ stała się niemalejąca.

Wejście

W pierwszej linii wejścia znajduje się jedna liczba całkowita $N$, określająca liczbę elementów w tablicy $A$ ($1 \le N \le 3 \cdot 10^5$). W drugiej linii znajduje się $N$ liczb całkowitych $A_1, \dots, A_N$: początkowe wartości elementów tablicy $A$ ($1 \le A_i \le 10^9$).

Wyjście

Wypisz minimalną liczbę operacji shuffle wymaganych do tego, aby tablica $A$ stała się niemalejąca.

Przykład

Wejście 1

3
2 2 5

Wyjście 1

0

Wejście 2

6
1 5 8 10 3 2

Wyjście 2

1