Not-So-Plain Sequence (Bonus)

Problem Description

This problem is an enhanced version of http://oj.daimayuan.top/problem/882; the only difference lies in the ranges of $n$ and $S_i$ (highlighted in red in the original statement).

For a sequence $\{S\}$, define $f(S) = \gcd(S_1, S_2, \dots, S_n)$.

We know that the $\gcd$ operation is associative: $\gcd(a, b, c, \dots) = \gcd(a, \gcd(b, c, \dots))$, so $f(S)$ can be computed easily.

However, Patricky thinks sequences with $f(S) = 1$ are too plain. Given $\{S\}$, he wants you to modify $\{S\}$ using the following operations so that $f(S) \ge 2$:

• Choose $i, i+1$ ($i \ne n$), change $\langle S_i, S_{i+1} \rangle$ to $\langle S_i - 1, S_{i+1} + 1 \rangle$.
• Choose $i, i+1$ ($i \ne n$), change $\langle S_i, S_{i+1} \rangle$ to $\langle S_i + 1, S_{i+1} - 1 \rangle$.

Find the minimum number of operations to make $f(S) \ge 2$, or report that it is impossible.

Input Format

The input consists of two lines. The first line contains an integer $n$, the size of $\{S\}$.

The next line contains $n$ space-separated integers, representing $S_1, S_2, \dots, S_n$.

Output Format

Output the minimum number of operations to make $f(S) \ge 2$. If impossible, output $-1$ on a single line.

Sample Input 1

3
4 8 5

Sample Output 1

9

Explanation: $[4, 8, 5] \xrightarrow{4} [0, 12, 5] \xrightarrow{5} [0, 17, 0]$.

Sample Input 2

4
0 5 15 10

Sample Output 2

0

Sample Input 3

6
1 2 3 4 5 6

Sample Output 3

2

Explanation: $[1, 2, 3, 4, 5, 6] \to [0, 3, 3, 4, 5, 6] \to [0, 3, 3, 3, 6, 6]$.

Constraints

• $1 \le n \le 10^{\color{red}{6}}$
• $S_i \in \color{red}{[0, 10^6]}$, but it is guaranteed that $\sum_{i=1}^n S_i \ge 1$, i.e. the elements are not all zero.