$\operatorname{mex}(S)$ を、集合 $S$ に含まれない最小の非負整数として定義します。
八九寺真宵(Mayoi Hachikuji)は $n$ 個の要素からなる配列 $a$ を持っており、これを広義単調増加(非減少順)に並べ替えたいと考えています。そのために、彼女は以下の操作を任意の回数($0$ 回でもよい)行うことができます:
- 整数 $i \in [1, \operatorname{length}(a) - 2]$ を選び、$a_i, a_{i+1}, a_{i+2}$ をそれらの $\operatorname{mex}$ で置き換える。この操作を行うと、配列の長さが $2$ 減少することに注意してください。
配列を非減少順にするために真宵が行う必要のある操作の最小回数を求めてください。不可能な場合は $-1$ を出力してください。
入力
入力の最初の行には、配列 $a$ の長さを表す整数 $n$ ($2 \le n \le 5 \cdot 10^5$) が与えられます。
次の行には、配列 $a$ の要素を表す $n$ 個の整数 $a_i$ ($0 \le a_i \le 10^9$) が与えられます。
出力
問題の答えを表す数値を $1$ つ出力してください。
入出力例
入力例 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