本题是 http://oj.daimayuan.top/problem/882 的加强版，差别仅在于 $n$ 与 $S_i$ 的取值。已使用红色字体标注题面中的区别。

关于序列 $\{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}{6}}$
• $S_i \in \color{red}{[0, 10^6]}$ 但保证 $\displaystyle \sum_{i = 1} ^n S_i \ge 1$，即元素不同时为 $0$。

样例 1 输入

3
4 8 5

样例 1 输出

9

解释：

$[4, 8, 5] \rightarrow^4 [0, 12, 5] \rightarrow^5 [0, 17, 0]$

样例 2 输入

4
0 5 15 10

样例 2 输出

0

样例 3 输入

6
1 2 3 4 5 6

样例 3 输出

2

解释：

$[1, 2, 3, 4, 5, 6] \rightarrow [0, 3, 3, 4, 5, 6] \rightarrow [0, 3, 3, 3, 6, 6]$