本题是 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]$