司马迁的史记

题目描述:

众所周知，司马迁是在牢房里编写出的史记。可是，现在有强迫症的司马迁遇到了一个艰巨的问题：就是竹板长度不一！

司马迁是要把字刻在竹板上的，于是这竹板长度不一让他很烦躁。不过司马迁可以用气功将任意一个竹板截任意长度单位，并把这一段接到相邻（左或右）的竹板上。注意一下，竹板围成一个圈，所以，有n个竹板，那么第一个竹板两边分别是第二个竹板和第n个竹板，第n个竹板两边分别是第一个竹板和第n-1个竹板。

现在司马迁想知道，最少要把多长的竹板换给其他竹板，n个竹板的长度才会一样？

输入格式:

第一行一个数n，表示有n个竹板围成一圈。

第二行n个数，第i个数ai表示第i个竹板的长度，数据保证所有竹板长度只和能被n整除。

输出格式:

一个数ans，表示至少要把多少的长度单位给别的竹板，所有竹板长度才会一样。

样例输入:

4
1 2 5 4

样例输出:

4

提示:

样例解释：

第3个竹板先给第2个竹板2个长度单位，

第2个竹板再给第1个竹板1个长度单位，

第4个竹板再给第1个竹板1个长度单位，

总共转了4个长度单位。

注意一下，每个竹板长度只能给相邻的竹板！

对于50%的数据，n<=500；

对于100%的数据，n<=100000，ai<=110；

时间限制: 1000ms
空间限制: 128MB

---

来源: by zhr