{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e♔♕♖♗♘♙♚♛♜♝♞♟\u003c/p\u003e\n\n\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e这是问题的较难版本。在这个版本中,$$$1 \\le n \\le 10^6$$$ 和 $$$0 \\leq a_i \\leq 10^6$$$。如果你锁定了这个问题,你可以破解它。但是只有在你锁定了两个问题的情况下,你才能破解前一个问题\u003c/span\u003e\u003c/p\u003e\u003cp\u003e圣诞节即将到来,我们的主角鲍勃正在为他的多年好友爱丽丝准备一份壮观的礼物。今年,他决定准备 $$$n$$$ 盒巧克力,编号从 $$$1$$$ 到 $$$n$$$。最初,第 $$$i$$$ 盒包含 $$$a_i$$$ 块巧克力。\u003c/p\u003e\u003cp\u003e由于鲍勃是一个典型的好人,他不会送给爱丽丝 $$$n$$$ 空盒子。换句话说,\u003cspan class\u003d\"tex-font-style-bf\"\u003e至少有一个 $$$a_1, a_2, \\ldots, a_n$$$ 是正数\u003c/span\u003e。由于爱丽丝不喜欢互质集,她只会在存在某个整数 $$$k \u0026gt; 1$$$ 使得每个盒子中的巧克力块数都能被 $$$k$$$ 整除时才会开心。注意,爱丽丝不介意存在一些空盒子。\u003c/p\u003e\u003cp\u003e爱丽丝的男朋友查理也是鲍勃的第二好朋友,所以他决定通过重新排列巧克力块来帮助鲍勃。每秒钟,查理可以从第 $$$i$$$ 盒中拿起一块巧克力并放入第 $$$i-1$$$ 或第 $$$i+1$$$ 盒(如果存在这样的盒子)。当然,他希望尽快帮助他的朋友。因此,他请你计算他需要让爱丽丝开心所需的最少秒数。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数 $$$n$$$($$$1 \\le n \\le 10^6$$$)— 巧克力盒的数量。\u003c/p\u003e\u003cp\u003e第二行包含 $$$n$$$ 个整数 $$$a_1, a_2, \\ldots, a_n$$$($$$0 \\le a_i \\le 10^6$$$)— 第 $$$i$$$ 盒中的巧克力块数。\u003c/p\u003e\u003cp\u003e保证 $$$a_1, a_2, \\ldots, a_n$$$ 中至少有一个是正数。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e如果查理无法让爱丽丝开心,输出 $$$-1$$$。\u003c/p\u003e\u003cp\u003e否则,输出一个整数 $$$x$$$ — 查理帮助鲍勃让爱丽丝开心所需的最少秒数。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n4 8 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n3 10 2 1 5\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n0 5 15 10\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e在第一个示例中,查理可以把所有巧克力块移到第二个盒子。每个盒子都能被 $$$17$$$ 整除。\u003c/p\u003e\u003cp\u003e在第二个示例中,查理可以把一块从第 $$$2$$$ 盒移到第 $$$3$$$ 盒,把一块从第 $$$4$$$ 盒移到第 $$$5$$$ 盒。每个盒子都能被 $$$3$$$ 整除。\u003c/p\u003e\u003cp\u003e在第三个示例中,每个盒子已经能被 $$$5$$$ 整除。\u003c/p\u003e\u003cp\u003e在第四个示例中,由于查理没有可用的移动,他无法帮助鲍勃让爱丽丝开心。\u003c/p\u003e"}}]}