关于序列 $\{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 输出

-1

Bonus: 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 !