Definiamo $\operatorname{mex}(S)$ come il minimo intero non negativo che non è contenuto in $S$.
Mayoi Hachikuji ha un array $a$ composto da $n$ elementi che vorrebbe fosse ordinato in ordine non decrescente. Per farlo, può eseguire la seguente operazione un qualsiasi numero di volte (eventualmente zero):
- Scegliere un intero $i \in [1, \operatorname{length}(a) - 2]$ e sostituire $a_i, a_{i+1}, a_{i+2}$ con il loro $\operatorname{mex}$. Si noti che dopo aver applicato questa operazione, la lunghezza dell'array diminuisce di $2$.
Trova il numero minimo di operazioni che Mayoi deve eseguire per rendere l'array ordinato in ordine non decrescente. Nel caso in cui sia impossibile farlo, stampa $-1$.
Input
La prima riga dell'input contiene l'intero $n$ ($2 \le n \le 5 \cdot 10^5$) — la lunghezza dell'array $a$.
La riga successiva contiene $n$ interi $a_i$ ($0 \le a_i \le 10^9$) — gli elementi dell'array $a$.
Output
Stampa un solo numero — la risposta al problema.
Esempi
Input di esempio 1
3 4 1 3
Output di esempio 1
1
Input di esempio 2
9 3 0 2 2 3 0 4 7 8
Output di esempio 2
2
Input di esempio 3
2 4 3
Output di esempio 3
-1