Zdefiniujmy $\operatorname{mex}(S)$ jako najmniejszą nieujemną liczbę całkowitą, która nie należy do zbioru $S$.
Mayoi Hachikuji ma tablicę $a$ składającą się z $n$ elementów, którą chciałaby posortować w porządku niemalejącym. W tym celu może wykonać następującą operację dowolną liczbę razy (być może zero):
- Wybierz liczbę całkowitą $i \in [1, \operatorname{length}(a) - 2]$ i zastąp elementy $a_i, a_{i+1}, a_{i+2}$ ich wartością $\operatorname{mex}$. Zauważ, że po wykonaniu tej operacji długość tablicy zmniejsza się o $2$.
Znajdź minimalną liczbę operacji, które Mayoi musi wykonać, aby tablica stała się posortowana w porządku niemalejącym. Jeśli jest to niemożliwe, wypisz $-1$.
Wejście
Pierwszy wiersz wejścia zawiera liczbę całkowitą $n$ ($2 \le n \le 5 \cdot 10^5$) — długość tablicy $a$.
Kolejny wiersz zawiera $n$ liczb całkowitych $a_i$ ($0 \le a_i \le 10^9$) — elementy tablicy $a$.
Wyjście
Wypisz jedną liczbę — odpowiedź dla zadania.
Przykłady
Przykładowe wejście 1
3 4 1 3
Przykładowe wyjście 1
1
Przykładowe wejście 2
9 3 0 2 2 3 0 4 7 8
Przykładowe wyjście 2
2
Przykładowe wejście 3
2 4 3
Przykładowe wyjście 3
-1