CF1254B2.Send Boxes to Alice (Hard Version)

This is the harder version of the problem. In this version, $1 \le n \le 10^6$ and $0 \leq a_i \leq 10^6$. You can hack this problem if you locked it. But you can hack the previous problem only if you locked both problems

Christmas is coming, and our protagonist, Bob, is preparing a spectacular present for his long-time best friend Alice. This year, he decides to prepare $n$ boxes of chocolate, numbered from $1$ to $n$. Initially, the $i$-th box contains $a_i$ chocolate pieces.

Since Bob is a typical nice guy, he will not send Alice $n$ empty boxes. In other words, at least one of $a_1, a_2, \ldots, a_n$ is positive. Since Alice dislikes coprime sets, she will be happy only if there exists some integer $k \gt 1$ such that the number of pieces in each box is divisible by $k$. Note that Alice won't mind if there exists some empty boxes.

Charlie, Alice's boyfriend, also is Bob's second best friend, so he decides to help Bob by rearranging the chocolate pieces. In one second, Charlie can pick up a piece in box $i$ and put it into either box $i-1$ or box $i+1$ (if such boxes exist). Of course, he wants to help his friend as quickly as possible. Therefore, he asks you to calculate the minimum number of seconds he would need to make Alice happy.

这是该问题的困难版本。在此版本中，$1 \le n \le 10^6$ 且 $0 \leq a_i \leq 10^6$。如果你锁定了本题，则可以对本题进行 Hack；但若你只想 Hack 上一题，则必须同时锁定本题和上一题。

圣诞节即将到来，我们的主角 Bob 正在为他多年以来最好的朋友 Alice 准备一份惊艳的礼物。今年，他决定准备 $n$ 盒巧克力，编号从 $1$ 到 $n$。初始时，第 $i$ 个盒子中有 $a_i$ 块巧克力。

由于 Bob 是一位典型的善良之人，他不会送给 Alice $n$ 个空盒子。换言之，$a_1, a_2, \ldots, a_n$ 中至少有一个是正数。又因 Alice 不喜欢互质的集合，她只有在存在某个整数 $k > 1$，使得每个盒子中的巧克力块数均能被 $k$ 整除时，才会感到开心。注意：Alice 并不介意某些盒子为空。

Charlie 是 Alice 的男朋友，同时也是 Bob 的第二好朋友，因此他决定帮助 Bob 重新分配巧克力。每秒钟，Charlie 可以从第 $i$ 个盒子中取出一块巧克力，并将其放入第 $i-1$ 或第 $i+1$ 个盒子中（如果这样的盒子存在）。当然，他希望尽可能快地帮助自己的朋友。因此，他请你计算出使 Alice 开心所需的最少秒数。

The first line contains a single integer $n$ ($1 \le n \le 10^6$) — the number of chocolate boxes.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^6$) — the number of chocolate pieces in the $i$-th box.

It is guaranteed that at least one of $a_1, a_2, \ldots, a_n$ is positive.

第一行包含一个整数 $n$（$1 \le n \le 10^6$）—— 巧克力盒子的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0 \le a_i \le 10^6$）—— 第 $i$ 个盒子中的巧克力块数量。

保证 $a_1, a_2, \ldots, a_n$ 中至少有一个为正数。

If there is no way for Charlie to make Alice happy, print $-1$.

Otherwise, print a single integer $x$ — the minimum number of seconds for Charlie to help Bob make Alice happy.

如果查理无法让爱丽丝开心，则输出 $-1$。

否则，输出一个整数 $x$ —— 查理帮助鲍勃让爱丽丝开心所需的最少秒数。

In the first example, Charlie can move all chocolate pieces to the second box. Each box will be divisible by $17$.

In the second example, Charlie can move a piece from box $2$ to box $3$ and a piece from box $4$ to box $5$. Each box will be divisible by $3$.

In the third example, each box is already divisible by $5$.

In the fourth example, since Charlie has no available move, he cannot help Bob make Alice happy.

在第一个例子中，查理可以将所有巧克力块移动到第二个盒子中。每个盒子中的巧克力块数都将能被 $17$ 整除。

在第二个例子中，查理可以将一个巧克力块从第 $2$ 个盒子移动到第 $3$ 个盒子，并将一个巧克力块从第 $4$ 个盒子移动到第 $5$ 个盒子。每个盒子中的巧克力块数都将能被 $3$ 整除。

在第三个例子中，每个盒子中的巧克力块数已经能被 $5$ 整除。

在第四个例子中，由于查理没有任何可行的操作，他无法帮助鲍勃让爱丽丝开心。