Problem1568--分饼干

1568: 分饼干

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 36  Solved: 4
[Submit] [Status] [Web Board] [Creator:]

Description

有n个小朋友坐成一圈,每人手上有若干块饼干。老师要求他们进行传递,使得每个人手上的饼干数量相同。
每个小朋友只能传递饼干给左右相邻的小朋友,保证饼干总量是n的整数倍,问最少传递多少块饼干可以满足老师的要求。

Input

多组输入。
每组数据第一行输入一个正整数n(n<=1e6),第二行输入n个正整数,按顺时针给出每个小朋友持有的饼干数。

Output

对于每组数据,输出被传递饼干数量的最小值,答案保证在64位整数范围内。

Sample Input

3 
10 10 10
4
1 1 4 2

Sample Output

0
3

Source/Category

困难