Étant donné un tableau d'entiers $A$ de taille $N$, l'opération de mélange (shuffle) est définie comme suit :

• Initialement, vous créez un tableau d'entiers vide $B$.
• Ensuite, tant que $A$ n'est pas vide, vous retirez soit l'élément le plus à gauche, soit l'élément le plus à droite de $A$, et vous ajoutez cette valeur à la fin de $B$.
• Si $A$ est vide, remplacez $A$ par $B$ et arrêtez.

Si l'opération de mélange est effectuée comme le montre l'image ci-dessus, la valeur du tableau $A$ est modifiée comme suit :

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

Soit $A_i$ le $i$-ième élément du tableau $A$. Lorsque la condition « si $1 \le i < j \le N$, alors $A_i \le A_j$ » est établie, on dit que le tableau $A$ est croissant de manière monotone.

Écrivez un programme qui, étant donné un tableau d'entiers $A$ de taille $N$, calcule le nombre minimum d'opérations de mélange nécessaires pour rendre le tableau $A$ croissant de manière monotone.

Entrée

La première ligne de l'entrée contient un entier $N$, le nombre d'éléments dans le tableau $A$ ($1 \le N \le 3 \cdot 10^5$). La deuxième ligne contient $N$ entiers $A_1, \dots, A_N$ : les valeurs initiales des éléments du tableau $A$ ($1 \le A_i \le 10^9$).

Sortie

Affichez le nombre minimum d'opérations de mélange nécessaires pour rendre le tableau $A$ croissant de manière monotone.

Exemples

Entrée 1

3
2 2 5

Sortie 1

0

Entrée 2

6
1 5 8 10 3 2

Sortie 2

1