有 n 个小朋友坐成一圈，每人有 a[i] 个糖果。

每人只能给左右两人传递糖果。

每人每次传递一个糖果代价为 1。

求使所有人获得均等糖果的最小代价。

输入格式

第一行输入一个正整数 n，表示小朋友的个数。

接下来 n 行，每行一个整数 a[i]，表示第 ii 个小朋友初始得到的糖果的颗数。

输出格式

输出一个整数，表示最小代价。

数据范围

1≤n≤1000000,

0≤a[i]≤2×109,

数据保证一定有解。

输入样例：

4
1
2
5
4

输出样例：

4

由题意知最终小孩的糖果数量一定是平均的，因此可以根据这个条件推导公式

推导过程和高斯消元非常类似，一步一步往上递推，这里是从下（即Xn）往上推的，前面最后一项+倒数第二项=后面倒数第二项，前面最后三项相加=后面倒数第三项......最后就可以解出每一项Xi的公式

把刚才得出的每一项Xi带入发现，形式都是X1减掉一个固定的常数，因此这里把常数用C1，C2....Cn来表示，而通过前面的计算，我们可以得出Ci的通项公式

好的，思路已经到这，下面就是用代码解方程的时间了

代码实现：

#include
#include
#include
using namespace std;
const int N=1000010;
int a[N];//a数组储存每个人获得糖果的数量
int c[N];//c[]是后面储存每个常量的数组
typedef long long ll;
int main()
{int n;scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&a[i]);ll sum=0;for(int i=1;i<=n;i++) sum+=a[i];ll avg=sum/n;for(int i=n;i>1;i--){c[i]=c[i+1]+avg-a[i];}c[1]=0;//到这一步就是相当于前面那题货仓找址一样，找出距离每个点距离相加最小的点一样，不懂看前面发的题sort(c+1,c+n+1);ll res=0;for(int i=1;i<=n;i++){res+=abs(c[i]-c[i+1>>1]);}cout<