我们定义 $\text{mex}(S)$ 为未包含在集合 $S$ 中的最小非负整数。

八九寺真宵（Mayoi Hachikuji）有一个由 $n$ 个元素组成的数组 $a$，她希望将其按非降序排序。为此，她可以执行以下操作任意次（可能为零次）：

• 选择整数 $i \in [1, \text{length}(a) - 2]$，并将 $a_i, a_{i+1}, a_{i+2}$ 替换为它们的 $\text{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