ACM的队员们最近对取石子游戏感到厌烦了，有一天QQ老师给他们介绍了一个新的游戏——分金币游戏。n个ACM的队员坐在一个圆桌上，每人有一定数量的金币，金币总数能被n整除。每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数相等。你的任务是求出被转手的金币数量的最小值。比如，n=4，且4个人的金币数分别为1，2，5，4时，只需转移4枚金币（第3个人给第2个人两枚金币，第2个人和第4个人分别给第1 个人1枚金币）即可实现每人手中的金币数目相等。

输入包含多组数据。每组数据第一行为整数n（n<=1 000），以下n行每行为一个整数，按逆时针顺序给出每个人拥有的金币数。输入结束标志为文件结束符（EOF）。

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