Definamos $\operatorname{mex}(S)$ como el menor entero no negativo que no está contenido en $S$.
Mayoi Hachikuji tiene un arreglo $a$ que consta de $n$ elementos y quiere que quede ordenado en orden no decreciente. Para lograrlo, puede realizar la siguiente operación cualquier número de veces (posiblemente cero):
- Elegir un entero $i \in [1, \operatorname{length}(a) - 2]$ y reemplazar $a_i, a_{i+1}, a_{i+2}$ por su $\operatorname{mex}$. Observa que después de aplicar esta operación, la longitud del arreglo disminuye en $2$.
Encuentra el número mínimo de operaciones que Mayoi necesita realizar para que el arreglo quede ordenado en orden no decreciente. En caso de que sea imposible lograrlo, imprime $-1$.
Entrada
La primera línea de la entrada contiene el entero $n$ ($2 \le n \le 5 \cdot 10^5$) — la longitud del arreglo $a$.
La siguiente línea contiene $n$ enteros $a_i$ ($0 \le a_i \le 10^9$) — los elementos del arreglo $a$.
Salida
Imprime un único número — la respuesta al problema.
Ejemplos
Entrada de ejemplo 1
3 4 1 3
Salida de ejemplo 1
1
Entrada de ejemplo 2
9 3 0 2 2 3 0 4 7 8
Salida de ejemplo 2
2
Entrada de ejemplo 3
2 4 3
Salida de ejemplo 3
-1