题目背景（可跳过剧情快步进入下面题目描述）

草帽一伙和小弟们（剧情需要）去了一座小岛探险，娜美留在梅利号上画海图，大家分开后每个人都带回来了很多金币。 路飞很想买肉吃，所以提议分赃了这些金币，索隆想买酒，山治想买食材，乌索普想买实用的小工具。 于是大家赞同了这个提议。 每个人可以给他左右相邻的人一些金币，最终使得每个人的金币数目相等。没想到分太慢了，娜美已经画完海图出来找大家了，结果看见分赃的众人，一气之下就把所有财宝都拿走了。

走之前还不忘揍了提出这个建议的路飞一顿。

题目描述（看前面就图一乐，做题还得看这里）

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

输入格式

第一行为整数n，以下n行每行一个正整数，按逆时针顺序给出每个人拥有的金币数。

输出格式

输出被转手金币数量的最小值。

数据范围

3≤n≤1000。 总金币数不超过10^9。

输入样例

4  
1 2 5 4  

输出样例

4

样例解释

设四个人编号为 1,2,3,4。 第 3 个人给第 2 个人 2 个金币（变成 1,4,3,4），第 2 个人和第 4 个人分别给第 1 个人 1 个金币。

Limitation

1s, 1024KiB for each test case.