关于序列 $\{S\}$ 定义 $f(S) = \gcd(S_1, S_2, \cdots, S_n)$。
我们熟知 $\gcd$ 运算具有结合律，即 $\gcd(a, b, c, \cdots) = \gcd(a, \gcd(b, c, \cdots))$，可以轻松算出 $f(S)$。
然而 Patricky 认为，那些 $f(S) = 1$ 的序列太过朴素。现在给定 $\{S\}$，他希望您能用下面的操作修改 $\{S\}$ 使得 $f(S) \ge 2$ ：
- 选择 $i, i + 1\;(i \ne n)$，将 $\langle S_i, S_{i + 1}\rangle$ 修改为 $\langle S_i - 1, S_{i + 1} + 1\rangle$
- 选择 $i, i + 1\;(i \ne n)$，将 $\langle S_i, S_{i + 1}\rangle$ 修改为 $\langle S_i + 1, S_{i + 1} - 1\rangle$
试回答使得 $f(S) \ge 2$ 的 最小 操作次数，或回答不可能。
输入格式
输入包含两行，第一行有一个整数 $n$，表示 $\{S\}$ 的大小。
接下来一行包含 $n$ 个用空格分隔的整数，依次表示 $S_1, S_2, \cdots, S_n$。
输出格式
输出使得 $f(S) \ge 2$ 的最小操作次数。如果不可能，则在一行中输出 $-1$。
数据规模
- $1 \le n \le 10 ^ {\color{red}{5}}$
- $S_i \in \color{red}{\{0, 1\}}$ 但保证 $\displaystyle \sum_{i = 1} ^n S_i \ge 1$，即元素不同时为 $0$。
样例 1 输入
3
1 0 1样例 1 输出
2解释：
$[1,0,1] \rightarrow [0, 1, 1] \rightarrow [0, 0, 2]$
样例 2 输入
3
0 0 1样例 2 输出
-1Bonus: How to solve the problem if $1 \le n \le 10 ^ 6,\;0 \le S_i \le 10^6$ ? Try http://oj.daimayuan.top/problem/883 !