Let us define $\operatorname{mex}(S)$ as the minimal non-negative integer which is not contained in $S$.
Mayoi Hachikuji has an array $a$ consisting of $n$ elements which she wants to be sorted in non-decreasing order. To do so, she can perform the following operation any number of times (possibly zero):
- Choose integer $i \in [1, \operatorname{length}(a) - 2]$ and replace $a_i, a_{i+1}, a_{i+2}$ with their $\operatorname{mex}$. Notice that after applying this operation, the length of the array decreases by $2$.
Find the minimum number of operations Mayoi needs to perform to make the array sorted in non-decreasing order. In case it is impossible to do so, output $-1$.
Input
First line of the input contains integer $n$ ($2 \le n \le 5 \cdot 10^5$) — length of the array $a$.
Next line contains $n$ integers $a_i$ ($0 \le a_i \le 10^9$) — elements of the array $a$.
Output
Output one number — the answer to the problem.
Examples
Sample Input 1
3 4 1 3
Sample Output 1
1
Sample Input 2
9 3 0 2 2 3 0 4 7 8
Sample Output 2
2
Sample Input 3
2 4 3
Sample Output 3
-1