← 返回题目列表

Codeforces · 1254/B2

B2. 给爱丽丝寄箱子(困难版)

中文机器翻译题面 查看原题

这是问题的更难版本。在此版本中,$$$1 \le n \le 10^6$$$ 和 $$$0 \leq a_i \leq 10^6$$$。如果你锁定了这个问题,你就可以解决这个问题。但只有当你锁定了这两个问题时,你才能破解前一个问题

圣诞节即将到来,我们的主角鲍勃正在为他的长期好友爱丽丝准备一份精美的礼物。今年,他决定准备$$$n$$$盒巧克力,编号从$$$1$$$到$$$n$$$。最初,第 $$$i$$$ 个盒子包含 $$$a_i$$$ 巧克力块。

由于鲍勃是一个典型的好人,他不会给爱丽丝寄$$$n$$$空盒子。换句话说,$$$a_1, a_2, \ldots, a_n$$$ 中至少有一个是正数。由于 Alice 不喜欢互质集,因此只有存在某个整数 $$$k > 1$$$ 使得每个盒子中的件数可以被 $$$k$$$ 整除时,她才会感到高兴。请注意,爱丽丝不会介意是否存在一些空盒子。

查理,爱丽丝的男朋友,也是鲍勃的第二好朋友,所以他决定通过重新排列巧克力块来帮助鲍勃。一秒钟内,查理可以拿起盒子 $$$i$$$ 中的一块,并将其放入盒子 $$$i-1$$$ 或盒子 $$$i+1$$$ 中(如果存在这样的盒子)。当然,他想尽快帮助他的朋友。因此,他要求你计算他需要多少秒才能让爱丽丝开心。

输入

第一行包含一个整数 $$$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$$$ 中至少有一个为正。

输出

如果查理没有办法让爱丽丝快乐,请打印$$$-1$$$。

否则,打印一个整数 $$$x$$$ — Charlie 帮助 Bob 让 Alice 开心的最小秒数。

示例

输入 #1

3
4 8 5

输出 #1

9

输入 #2

5
3 10 2 1 5

输出 #2

2

输入 #3

4
0 5 15 10

输出 #3

0

输入#4

1
1

输出#4

-1

注意

在第一个示例中,Charlie 可以将所有巧克力块移动到第二个盒子中。每个盒子都可以被$$$17$$$整除。

在第二个示例中,Charlie 可以将棋子从盒子 $$$2$$$ 移动到盒子 $$$3$$$,并将棋子从盒子 $$$4$$$ 移动到盒子 $$$5$$$。每个盒子都可以被$$$3$$$整除。

在第三个示例中,每个框已可被 $$$5$$$ 整除。

在第四个示例中,由于 Charlie 没有可用的动作,因此他无法帮助 Bob 让 Alice 开心。