AlanashKO aime l'argent. À la veille du Nouvel An, il a reçu $N$ billets de banque. La valeur nominale de chaque billet est un entier strictement positif. En jouant, AlanashKO a disposé tous les billets en une rangée et les a numérotés de gauche à droite de $1$ à $N$. Il a ensuite décidé de trier tous les billets par ordre croissant au sens large.

Pour cela, AlanashKO procède ainsi : il partage d'abord les billets en un ou plusieurs sous-segments disjoints, chaque billet appartenant à un sous-segment. Ensuite, tous les sous-segments sont insérés à tour de rôle dans une nouvelle rangée, dans leur ordre de gauche à droite : le sous-segment le plus à gauche (le premier) est inséré en premier, puis le suivant, et ainsi de suite. Chaque sous-segment est inséré soit entre deux billets quelconques, soit à l'une des deux extrémités de la nouvelle rangée actuelle. L'ordre des billets au sein du sous-segment ne change pas lors de l'insertion.

AlanashKO souhaite minimiser le nombre de sous-segments lui permettant finalement de trier les billets par ordre croissant au sens large. Aidez-le à trouver cette valeur.

Entrée

La première ligne contient un entier strictement positif $N$ ($1 \le N \le 10^6$), le nombre de billets. La ligne suivante contient $N$ entiers strictement positifs $a_i$ ($1 \le a_i \le 10^6$), la valeur du $i$-ième billet.

Sortie

Affichez sur une seule ligne un entier : le nombre minimal de sous-segments permettant à AlanashKO de trier les billets.

Sous-tâches

Ce problème comprend quatre sous-tâches :

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

Une sous-tâche ne rapporte des points que si la solution réussit également toutes les sous-tâches précédentes.

Exemples

Entrée 1

6
3 6 4 5 1 2

Sortie 1

3

Remarque

Un sous-segment est une suite d'éléments consécutifs.

Considérons l'exemple :

La réponse minimale correspond à un découpage en $3$ sous-segments : |3 6|4 5|1 2| (les barres indiquent les limites des sous-segments).

Après la première étape : la rangée initiale est |4 5|1 2|, et la nouvelle rangée est |3 6|.

À la deuxième étape, le sous-segment |4 5| est inséré entre $3$ et $6$.

Après la deuxième étape : la rangée initiale est |1 2|, et la nouvelle rangée est |3 4 5 6|.

Enfin, le sous-segment |1 2| est inséré au début de la nouvelle rangée, donnant |1 2 3 4 5 6|.