UVA-11300

#include <iostream>
#include "bits/stdc++.h"
#define ll long long
using namespace std;

int main() {
    int N;
    while(scanf("%d",&N) == 1)
    {
        vector<ll>a(N+1),c(N,0);
        ll tmp = 0;
        for(int i = 1;i<=N;i++)
        {
            cin>>a[i];
            tmp += a[i];
        }
        tmp /= N;

        for(int i = 1;i<N;i++)
        {
            c[i] = c[i-1] + a[i] - tmp;
        }
        sort(c.begin(),c.end());

        ll x = c[N/2];
        ll ans = 0;
        for(int i = 0;i<N;i++)
        {
            ans += abs(x - c[i]);
        }
        cout<<ans<<endl;
    }
    return 0;
}