Skilgreinum $\operatorname{mex}(S)$ sem minnstu óneikvæðu heiltöluna sem er ekki í menginu $S$.
Mayoi Hachikuji er með fylki $a$ sem samanstendur af $n$ stökum og hún vill að það sé raðað í ekki-minnkandi röð. Til þess getur hún framkvæmt eftirfarandi aðgerð hversu oft sem er (hugsanlega núll sinnum):
- Veldu heiltölu $i \in [1, \operatorname{length}(a) - 2]$ og skiptu $a_i, a_{i+1}, a_{i+2}$ út fyrir $\operatorname{mex}$ þeirra. Taktu eftir að eftir þessa aðgerð minnkar lengd fylkisins um $2$.
Finndu lágmarksfjölda aðgerða sem Mayoi þarf að framkvæma til að gera fylkið raðað í ekki-minnkandi röð. Ef það er ómögulegt skal prenta $-1$.
Inntak
Fyrsta lína inntaksins inniheldur heiltölu $n$ ($2 \le n \le 5 \cdot 10^5$) — lengd fylkisins $a$.
Næsta lína inniheldur $n$ heiltölur $a_i$ ($0 \le a_i \le 10^9$) — stök fylkisins $a$.
Úttak
Prentaðu eina tölu — svarið við dæminu.
Dæmi
Sýnidæmi 1 — Inntak
3 4 1 3
Sýnidæmi 1 — Úttak
1
Sýnidæmi 2 — Inntak
9 3 0 2 2 3 0 4 7 8
Sýnidæmi 2 — Úttak
2
Sýnidæmi 3 — Inntak
2 4 3
Sýnidæmi 3 — Úttak
-1