Wir definieren $\operatorname{mex}(S)$ als die kleinste nichtnegative ganze Zahl, die nicht in $S$ enthalten ist.
Mayoi Hachikuji hat ein Array $a$ bestehend aus $n$ Elementen, das sie in nichtfallender Reihenfolge sortieren möchte. Dazu kann sie die folgende Operation beliebig oft (möglicherweise nullmal) ausführen:
- Wähle eine ganze Zahl $i \in [1, \operatorname{length}(a) - 2]$ und ersetze $a_i, a_{i+1}, a_{i+2}$ durch ihr $\operatorname{mex}$. Beachte, dass sich die Länge des Arrays nach Anwendung dieser Operation um $2$ verringert.
Finde die minimale Anzahl an Operationen, die Mayoi ausführen muss, damit das Array in nichtfallender Reihenfolge sortiert ist. Falls dies unmöglich ist, gib $-1$ aus.
Eingabe
Die erste Zeile der Eingabe enthält die ganze Zahl $n$ ($2 \le n \le 5 \cdot 10^5$) — die Länge des Arrays $a$.
Die nächste Zeile enthält $n$ ganze Zahlen $a_i$ ($0 \le a_i \le 10^9$) — die Elemente des Arrays $a$.
Ausgabe
Gib eine einzige Zahl aus — die Antwort auf die Aufgabe.
Beispiele
Beispieleingabe 1
3 4 1 3
Beispielausgabe 1
1
Beispieleingabe 2
9 3 0 2 2 3 0 4 7 8
Beispielausgabe 2
2
Beispieleingabe 3
2 4 3
Beispielausgabe 3
-1