La oss definere $\operatorname{mex}(S)$ som det minste ikke-negative heltallet som ikke er inneholdt i $S$.
Mayoi Hachikuji har en tabell $a$ bestående av $n$ elementer som hun ønsker å få sortert i ikke-avtakende rekkefølge. For å gjøre dette kan hun utføre følgende operasjon så mange ganger hun vil (muligens null):
- Velg et heltall $i \in [1, \operatorname{length}(a) - 2]$ og erstatt $a_i, a_{i+1}, a_{i+2}$ med deres $\operatorname{mex}$. Legg merke til at etter at denne operasjonen er utført, reduseres lengden på tabellen med $2$.
Finn det minste antallet operasjoner Mayoi må utføre for å gjøre tabellen sortert i ikke-avtakende rekkefølge. Dersom det er umulig å få til dette, skriv ut $-1$.
Inndata
Den første linjen i inndataene inneholder heltallet $n$ ($2 \le n \le 5 \cdot 10^5$) — lengden på tabellen $a$.
Neste linje inneholder $n$ heltall $a_i$ ($0 \le a_i \le 10^9$) — elementene i tabellen $a$.
Utdata
Skriv ut ett tall — svaret på oppgaven.
Eksempler
Eksempelinndata 1
3 4 1 3
Eksempelutdata 1
1
Eksempelinndata 2
9 3 0 2 2 3 0 4 7 8
Eksempelutdata 2
2
Eksempelinndata 3
2 4 3
Eksempelutdata 3
-1