Låt oss definiera $\operatorname{mex}(S)$ som det minsta icke-negativa heltalet som inte ingår i $S$.
Mayoi Hachikuji har en array $a$ bestående av $n$ element som hon vill ska vara sorterad i icke-avtagande ordning. För att göra detta kan hon utföra följande operation valfritt antal gånger (möjligen noll):
- Välj ett heltal $i \in [1, \operatorname{length}(a) - 2]$ och ersätt $a_i, a_{i+1}, a_{i+2}$ med deras $\operatorname{mex}$. Observera att efter att denna operation har utförts minskar arrayens längd med $2$.
Hitta det minsta antalet operationer Mayoi behöver utföra för att göra arrayen sorterad i icke-avtagande ordning. Om det är omöjligt att göra detta, skriv ut $-1$.
Indata
Den första raden i indatan innehåller heltalet $n$ ($2 \le n \le 5 \cdot 10^5$) — längden på arrayen $a$.
Nästa rad innehåller $n$ heltal $a_i$ ($0 \le a_i \le 10^9$) — elementen i arrayen $a$.
Utdata
Skriv ut ett tal — svaret på problemet.
Exempel
Exempelindata 1
3 4 1 3
Exempelutdata 1
1
Exempelindata 2
9 3 0 2 2 3 0 4 7 8
Exempelutdata 2
2
Exempelindata 3
2 4 3
Exempelutdata 3
-1