Problem1196--圆桌骑士

1196: 圆桌骑士

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

Description

Saber召集了ｎ个骑士开会，n个人绕着桌子围成一圈，每个人手上都有一些圣晶石，圣晶石的总数能够被 n 整除，每位骑士只能给左右相邻的骑士圣晶石，问最少交换几个圣晶石，最终使得每个人手上的圣晶石一样多？

Input

输入包含多组数据。
每组数据第一行为一个整数 n( n<=1e6) ,一下n行每行为一个整数，按逆时针给出每位骑士拥有的圣晶石数。

Output

对于每组数据，输出被转手圣晶石数量的最小值,答案保证在64bit的范围内。

Sample Input 

3
100
100
100
4
1
2
5
4

Sample Output 

0
4

Source/Category

困难 数学 
[Submit] [Status]