#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <algorithm>

#include <queue>

#include <string>

#include <iostream>

#include <vector>

#define inf 0x3f3f3f3f

using namespace std;

const int maxn = 3e5 + ;

typedef long long ll;

struct edge

{

    int u, v, c, f, cost;

    edge(int u=,int v=,int c=,int f=,int cost=):u(u),v(v),c(c),f(f),cost(cost){}

};

vector<edge>e;

vector<int>G[maxn];

int a[maxn], p[maxn], inq[maxn], d[maxn], n, m;

void init(int n)

{

    for (int i = ; i <= n; i++) G[i].clear();

    e.clear();

}

void addedge(int u,int v,int c,int cost)

{

    e.push_back(edge(u, v, c, , cost));

    e.push_back(edge(v, u, , , -cost));

    int m = e.size();

    G[u].push_back(m - );

    G[v].push_back(m - );

}

bool spfa(int s,int t,int &flow,ll &cost)

{

    memset(d, inf, sizeof(d));

    memset(inq, , sizeof(inq));

    d[s] = , inq[s] = ;

    p[s] = , a[s] = inf;

    queue<int>que;

    que.push(s);

    while(!que.empty())

    {

        int u = que.front(); que.pop();

        inq[u] = ;

        for(int i=;i<G[u].size();i++)

        {

            edge &now = e[G[u][i]];

            int v = now.v;

            if(now.c>now.f&&d[v]>d[u]+now.cost)

            {

                d[v] = d[u] + now.cost;

                p[v] = G[u][i];

                a[v] = min(a[u], now.c - now.f);

                if (!inq[v]) que.push(v), inq[v] = ;

            }

        }

    }

    if (d[t] == inf) return false;

    flow += a[t];

    cost += d[t] * 1ll * a[t];

    for(int u=t;u!=s;u=e[p[u]].u)

    {

        e[p[u]].f += a[t];

        e[p[u] ^ ].f -= a[t];

    }

    return true;

}

int MincostMaxflow(int s,int t,ll &cost)

{

    cost = ;

    int flow = ;

    while (spfa(s, t, flow, cost));

    return flow;

}

int main() {

    int n, sum = ;

    scanf("%d", &n);

    for (int i = ; i <= n; i++) scanf("%d", &a[i]), sum += a[i];

    sum /= n;

    int s = , t = n + ;

    for(int i=;i<=n;i++)

    {

        if (a[i] > sum) addedge(s, i, a[i] - sum, );

        else addedge(i, t, sum - a[i], );

        if(i==)

        {

            addedge(, , inf, );

            addedge(, n, inf, );

        }

        else if(i==n)

        {

            addedge(n, , inf, );

            addedge(n, n - , inf, );

        }

        else

        {

            addedge(i, i + , inf, );

            addedge(i, i - , inf, );

        }

    }

    ll ans = ;

    MincostMaxflow(s, t, ans);

    printf("%lld\n", ans);

    return ;

}