学步园

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000001;
long long n, sum, ans, a[maxn], need[maxn];
inline void solve(long long a[], long long ave){
    need[1] = ave - a[1];
    for (int i = 2; i <= n; i++)
        need[i] = need[i - 1] + ave - a[i];
    sort(need + 1, need + n + 1);
    for (int i = 1; i <= n; i++)
        ans += (long long)abs(need[i] - need[(n + 1) >> 1]);
}

int main(){
    scanf("%lld", &n);
    for (int i = 1; i <= n; i++)
        scanf("%lld", &a[i]), sum += a[i];
    solve(a, sum / n);
    printf("%lld", ans);
    return 0;
}