这是问题的简单版本。在此版本中,$$$1 \le n \le 10^5$$$ 和 $$$0 \le a_i \le 1$$$。只有解决并锁定这两个问题,你才能解决这个问题。
圣诞节即将到来,我们的主角鲍勃正在为他的长期好友爱丽丝准备一份精美的礼物。今年,他决定准备$$$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^5$$$) — 巧克力盒的数量。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 1$$$) — 第 $$$i$$$ 个盒子中巧克力的数量。
保证 $$$a_1, a_2, \ldots, a_n$$$ 中至少有一个为正。
输出
如果 Charlie 没有办法让 Alice 开心,则打印 $$$-1$$$。
否则,打印一个整数 $$$x$$$ — Charlie 帮助 Bob 让 Alice 开心的最小秒数。
示例
输入 #1
3 1 0 1
输出 #1
2
输入 #2
1 1
输出 #2
-1