#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long
#define N 114514
using namespace std;
int n,s,t,ansc,a[N],head[N],to[N],nxt[N],val[N],cst[N],tot,ave,d[N];
bool vis[N];
void add(int u,int v,int w,int c){
	to[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
	val[tot]=w;
	cst[tot]=c;
	to[++tot]=u;
	nxt[tot]=head[v];
	head[v]=tot;
	val[tot]=0;
	cst[tot]=-c;
}
bool spfa(){
	memset(vis,0,sizeof(vis));
	memset(d,0x3f,sizeof(d));
	queue<int>q;
	q.push(s);
	d[s]=0;
	while(!q.empty()){
		int x=q.front();q.pop();
		//printf("%lld\n",x);
		vis[x]=0;
		for(int i=head[x];i;i=nxt[i]){
			if(!val[i])continue;
			int y=to[i],w=cst[i];
			if(d[y]>d[x]+w){
				d[y]=d[x]+w;
				if(!vis[y])vis[y]=1,q.push(y);
			}
		}
	}
	return d[t]!=inf;
}
int dfs(int x,int a){
	//printf("%lld\n",x);
	if(!a||x==t)return a;
	int res=a;
	vis[x]=1;
	for(int i=head[x];i;i=nxt[i]){
		int y=to[i];
		if(val[i]&&!vis[y]&&d[y]==d[x]+cst[i]){
			int tmp=dfs(y,min(val[i],res));
			res-=tmp;
			val[i]-=tmp;
			val[i^1]+=tmp;
			ansc+=tmp*cst[i];
			if(res<=0){
				vis[x]=0;
				return a; 
			}
		}
	}
	vis[x]=0;
	if(res==a)vis[x]=1;
	return a-res;
}
void dinic(){
	while(spfa()){
		memset(vis,0,sizeof(vis));
		while(dfs(s,inf));
	}
}
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),ave+=a[i];
	ave/=n;
	s=0,t=n+1;
	for(int i=1;i<=n;i++){
		if(a[i]<ave)add(s,i,ave-a[i],0);
		else if(a[i]>ave)add(i,t,a[i]-ave,0);
		if(i==1){
			add(1,n,inf,1);
			add(n,1,inf,1);
		}else{
			add(i-1,i,inf,1);
			add(i,i-1,inf,1);
		}
	}
	dinic();
	printf("%lld",ansc);
	return 0;
}