我哋定義 $\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