Description
N个村民围坐在一张圆桌旁，每个人手里都有一定数量的金币，所有金币的总数能够被N整除。每个人都可以给他的左右相邻的人一些金币，最终使得每个人的金币数目相等。
你的任务是计算出必须被转手的金币数量的最小值。
例如N=4时，假设4个人开始的金币数量分别为1,2,5,4，只需转手4枚金币（第3个人给第2个人两枚金币，第2个人和第4个人分别给第1个人1枚金币）即可实现每人手中的金币数目相等
Input
输入包含多组数据。
每组数据第一行是一个整数N（N≤1000000）
接下来N行每行一个整数，按逆时针顺序给出每个人拥有的金币数。
Output
对于每组数据，输出被转手金币数量的最小值。输入保证这个值在64位无符号整数范围内。