Définissons $\operatorname{mex}(S)$ comme le plus petit entier naturel qui n'appartient pas à $S$.
Mayoi Hachikuji possède un tableau $a$ composé de $n$ éléments qu'elle souhaite trier par ordre croissant au sens large (non décroissant). Pour ce faire, elle peut effectuer l'opération suivante autant de fois qu'elle le souhaite (éventuellement zéro fois) :
- Choisir un entier $i \in [1, \operatorname{length}(a) - 2]$ et remplacer $a_i, a_{i+1}, a_{i+2}$ par leur $\operatorname{mex}$. Remarquez qu'après l'application de cette opération, la longueur du tableau diminue de $2$.
Trouvez le nombre minimal d'opérations que Mayoi doit effectuer pour que le tableau soit trié par ordre non décroissant. S'il est impossible d'y parvenir, affichez $-1$.
Entrée
La première ligne de l'entrée contient l'entier $n$ ($2 \le n \le 5 \cdot 10^5$) — la longueur du tableau $a$.
La ligne suivante contient $n$ entiers $a_i$ ($0 \le a_i \le 10^9$) — les éléments du tableau $a$.
Sortie
Affichez un seul nombre — la réponse au problème.
Exemples
Entrée d'exemple 1
3 4 1 3
Sortie d'exemple 1
1
Entrée d'exemple 2
9 3 0 2 2 3 0 4 7 8
Sortie d'exemple 2
2
Entrée d'exemple 3
2 4 3
Sortie d'exemple 3
-1