← 返回题目列表

Codeforces · 440/B

B. 平衡器

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

Petya 有 k 根火柴,放在从左到右排成一行的 n 个火柴盒中。我们知道 k 可以被 n 整除。 Petya 希望所有盒子里的火柴数量相同。为此,他可以一次性将一根火柴从其盒子移到相邻的盒子中。他需要多少次这样的动作才能达到所需的配置?

输入

第一行包含整数 n (1 ≤ n ≤ 50000)。第二行包含n个不超过109的非负数,第i个写入的数字是第i个火柴盒中的匹配数。保证匹配总数能被n整除。

输出

打印总的最小移动次数。

示例

输入 #1

6
1 6 2 5 3 7

输出 #1

12