时间限制：1秒　　内存限制：256M

---

【题目描述】

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

【输入格式】

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

【输出格式】

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

【输入输出样例】

　Input

4
1
2
5
4

　Output

4

【数据限制】

　　 测试点 1~5：\(n≤5\)，总金币数\(≤100\)
　　 测试点 6~10：\(n≤100\)，总金币数\(≤1000\)
　　 测试点 11~15：\(n≤2000\)，总金币数\(≤10^5\)
　　 测试点 16~20：\(n≤30000\)，总金币数\(≤10^7\)
　　 测试点 21~25：\(n≤100000\)，总金币数\(≤10^9\)

【来源】

　　Mr.he