我們定義 $\operatorname{mex}(S)$ 為未包含在集合 $S$ 中的最小非負整數。
八九寺真宵(Mayoi Hachikuji)有一個由 $n$ 個元素組成的陣列 $a$,她希望將其按非遞減順序排序。為此,她可以執行以下操作任意次(可能為零次):
- 選擇整數 $i \in [1, \operatorname{length}(a) - 2]$,並將 $a_i, a_{i+1}, a_{i+2}$ 替換為它們的 $\operatorname{mex}$。請注意,在執行此操作後,陣列的長度會減少 $2$。
求出真宵使陣列按非遞減順序排序所需執行的最少操作次數。如果無法做到,請輸出 $-1$。
輸入格式
輸入的第一行包含一個整數 $n$ ($2 \le n \le 5 \cdot 10^5$) —— 陣列 $a$ 的長度。
下一行包含 $n$ 個整數 $a_i$ ($0 \le a_i \le 10^9$) —— 陣列 $a$ 的元素。
輸出格式
輸出一個整數 —— 問題的答案。
範例
範例輸入 1
3 4 1 3
範例輸出 1
1
範例輸入 2
9 3 0 2 2 3 0 4 7 8
範例輸出 2
2
範例輸入 3
2 4 3
範例輸出 3
-1