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
Petya 有 k 根火柴,放在从左到右排成一行的 n 个火柴盒中。我们知道 k 可以被 n 整除。 Petya 希望所有盒子里的火柴数量相同。为此,他可以一次性将一根火柴从其盒子移到相邻的盒子中。他需要多少次这样的动作才能达到所需的配置?
第一行包含整数 n (1 ≤ n ≤ 50000)。第二行包含n个不超过109的非负数,第i个写入的数字是第i个火柴盒中的匹配数。保证匹配总数能被n整除。
打印总的最小移动次数。
6 1 6 2 5 3 7
12