Määritellään $\operatorname{mex}(S)$ pienimmäksi epänegatiiviseksi kokonaisluvuksi, joka ei sisälly joukkoon $S$.
Mayoi Hachikujilla on $n$ alkiosta koostuva taulukko $a$, jonka hän haluaa järjestää ei-vähenevään järjestykseen. Tehdäkseen niin hän voi suorittaa seuraavan operaation mielivaltaisen määrän kertoja (mahdollisesti nolla kertaa):
- Valitse kokonaisluku $i \in [1, \operatorname{length}(a) - 2]$ ja korvaa alkiot $a_i, a_{i+1}, a_{i+2}$ niiden arvolla $\operatorname{mex}$. Huomaa, että tämän operaation suorittamisen jälkeen taulukon pituus pienenee luvulla $2$.
Etsi pienin määrä operaatioita, jotka Mayoin täytyy suorittaa saadakseen taulukon ei-vähenevään järjestykseen. Jos tämä on mahdotonta, tulosta $-1$.
Syöte
Syötteen ensimmäinen rivi sisältää kokonaisluvun $n$ ($2 \le n \le 5 \cdot 10^5$) — taulukon $a$ pituuden.
Seuraava rivi sisältää $n$ kokonaislukua $a_i$ ($0 \le a_i \le 10^9$) — taulukon $a$ alkiot.
Tuloste
Tulosta yksi luku — tehtävän vastaus.
Esimerkit
Esimerkkisyöte 1
3 4 1 3
Esimerkkituloste 1
1
Esimerkkisyöte 2
9 3 0 2 2 3 0 4 7 8
Esimerkkituloste 2
2
Esimerkkisyöte 3
2 4 3
Esimerkkituloste 3
-1