#include<cmath>
#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=500+10,M=1000+10;
const int inf=(1ll<<25);
int num=0,id[N],a[N],sum;
int n,m,s,t;
int tot,head[N],than[M<<1],to[M<<1],cost[M<<1],val[M<<1];
void add(int x,int y,int v,int c){
//	printf("%d %d\n",x,y);
	++tot;to[tot]=y;val[tot]=v;cost[tot]=c;than[tot]=head[x];head[x]=tot;
	++tot;to[tot]=x;val[tot]=0;cost[tot]=-c;than[tot]=head[y];head[y]=tot;
}
int e[N],dis[N],ans=0,In[N],co[N];
queue<int>q;
int bfs(){
	for(int i=0;i<=num*2+2;i++)e[i]=dis[i]=In[i]=0,co[i]=inf;
	
	q.push(s);dis[s]=inf;co[s]=0;In[s]=1;
	while(!q.empty()){
		int x=q.front();q.pop();In[x]=0;
		//printf("%d\n",x);
		for(int i=head[x];i;i=than[i]){
			if(val[i]<=0)continue;
			int y=to[i];
			if(co[y]>co[x]+cost[i]){
				co[y]=co[x]+cost[i];
				e[y]=i^1;
				dis[y]=min(dis[x],val[i]);
				if(In[y]==0){
					In[y]=1;
					q.push(y);
				}
			}
		}
	}
	return co[t]==inf?0:1;
}
int EK(){
	int ans=0;
	while(bfs()){
		ans+=dis[t]*co[t];
	//	printf("%d\n",ans);
		int x=t;
		do{
			int j=e[x];
			val[j]+=dis[t];
			val[j^1]-=dis[t];
			x=to[j];
			//printf("%d %d %d\n",x,s,t);
		}while(x!=s);
	}
	printf("%d\n",ans);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		sum+=a[i];
	}
	sum/=n;
	for(int i=1;i<=n;i++)a[i]-=sum;
	s=++num;
	for(int i=1;i<=n;i++)if(a[i]>=0)id[i]=++num;
	for(int i=1;i<=n;i++)if(a[i]<0)id[i]=++num;
	t=++num;
	tot=1;
	for(int i=1;i<=n;i++){
		if(a[i]>0)add(s,id[i],a[i],0);
		else if(a[i]<0)add(id[i],t,-a[i],0);
		add(id[i],id[i]+num,inf,0);
		if(i==1)add(id[i],id[n],inf,1),add(id[i]+num,id[i+1],inf,1);
		else if(i==n)add(id[i]+num,id[1],inf,1),add(id[i],id[i-1],inf,1);
		else add(id[i]+num,id[i+1],inf,1),add(id[i],id[i-1],inf,1);
	}
	EK();
	return 0;
}