分金币

【题目描述】

圆桌旁坐着$n$个人，每个人有一定数量的金币，金币数总能被$n$整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数相等。你的任务是求出被转手的金币数量最小值。

比如，$n=4$，且4个人的金币数分别是1,2,5,4时，只需转移4枚金币(第3个人给第2个人2枚金币，第2个人和第4个人分别给第一个人1枚金币)即可实现每人手中的金币数相等。

【输入格式】

输入包括多组数据。每组数据的第一行为整数$n(n≤10^6)$，以下$n$行每行为一个整数，按逆时针的顺序给出每个人拥有的金币数。输入结束标志为文件结束符(EOF).

【输出格式】

对于每组数据，输出被转手的金币数量的最小值。

输入保证这个值在64位无符号整数范围内。

【样例输入】

3
100
100
100
4
1
2
5
4

【样例输出】

0
4

【题目来源】

Spreading the Wealth ,UVa 11300