#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,st,ed;
struct N{
	ll y,v,f,nxt;
}e[100010];
int head[410],tsp=1;
void add(int x,int y,int v,int f){
	e[++tsp]={y,v,f,head[x]};head[x]=tsp;
	e[++tsp]={x,0,-f,head[y]};head[y]=tsp;
}
ll h[410];
int now[410],vis[410];
bool bfs(){
	memcpy(now,head,sizeof(now));
	memset(h,0x3f,sizeof(h));
	memset(vis,0,sizeof(vis));
	queue<int> q;
	q.push(st);
	h[st]=0;
	vis[st]=1;
	while(!q.empty()){
		int x=q.front();
		q.pop();
		vis[x]=0;
		for(int i=head[x];i;i=e[i].nxt){
			ll y=e[i].y,v=e[i].v,f=e[i].f;
			if(h[y]>h[x]+f&&v){
				h[y]=h[x]+f;
				if(!vis[y]){
					vis[y]=1;q.push(y);
				}
			}
		}
	}
	memset(vis,0,sizeof(vis));
	return h[ed]!=0x3f3f3f3f3f3f3f3f;
}
ll ans1,ans2;
ll dinic(int x,ll s){
	vis[x]=1;
	if(x==ed){
		ans2+=s*h[x];
		return s;
	}
	ll ans=0;
	for(int i=now[x];i;i=e[i].nxt){
		now[x]=i;
		ll y=e[i].y,v=e[i].v,f=e[i].f;
		if(vis[y])continue;
		if(h[y]==h[x]+f&&v){
			ll k=dinic(y,min(s-ans,v));
			e[i].v-=k;
			e[i^1].v+=k;
			ans+=k;
			if(ans==s)return s;
		}
	}
	if(ans)vis[x]=0;
	return ans;
}
int a[110];
vector<int> v1,v2;
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	st=0;ed=n+1;
	ll sum=0;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum+=a[i];
	}
	sum/=n;
	for(int i=1;i<=n;i++){
		a[i]-=sum;
		if(a[i]>0)v1.push_back(i);
		else if(a[i]<0)v2.push_back(i),a[i]=-a[i];
	}
	for(int i:v1){
		add(st,i,a[i],0);
	}
	for(int i:v2){
		add(i,ed,a[i],0);
	}
	for(int i:v1){
		for(int j:v2){
			add(i,j,min(a[i],a[j]),(i>j?min(i-j,j+n-i):min(j-i,i+n-j)));
		}
	}
	while(bfs()){
		ans1+=dinic(st,1ll<<62);
	}
	cout<<ans2<<'\n'; 
	return 0;
}

#include<cstdio>
#include<cstring>
using  namespace  std;
struct  node
{
	int  y,c,d,next,other;
}a[21000];int  len,last[210],n,st,ed,sum,cost;
int  list[210],head,tail,d[210];
bool  v[210];
void  ins(int  x,int  y,int  c,int  d)
{
	len++;
	a[len].y=y;a[len].c=c;a[len].d=d;
	a[len].next=last[x];last[x]=len;
	len++;
	a[len].y=x;a[len].c=0;a[len].d=-d;
	a[len].next=last[y];last[y]=len;
	a[len].other=len-1;
	a[len-1].other=len;
}
bool  spfa()
{
	memset(d,20,sizeof(d));d[ed]=0;v[ed]=false;
	head=1;tail=2;list[head]=ed;
	int  inf=d[ed+1];
	while(head!=tail)
	{
		int  x=list[head];
		for(int  k=last[x];k;k=a[k].next)
		{
			int  y=a[k].y,kl=a[k].other;
			if(a[kl].c>0    &&  d[y]>d[x]-a[k].d)
			{
				d[y]=d[x]-a[k].d;
				if(v[y]==true)
				{
					v[y]=false;
					if(d[list[head+1]]>d[y])
					{
						int  all=head;
						head--;if(head==0)head=n;
						list[head]=list[all];list[all]=y;
					}
					else
					{
						list[tail++]=y;
						if(tail==n+1)tail=1;
					}
				}
			}
		}
		head++;if(head==n+1)head=1;
		v[x]=true;
	}
	return  d[st]!=inf;
}
inline  int  mymin(int  x,int  y){return  x<y?x:y;}
int  find(int  x,int  f)
{
	v[x]=false;
	if(x==ed){v[x]=true;return  f;}
	int  ans=0,t=0;
	for(int  k=last[x];k;k=a[k].next)
	{
		int  y=a[k].y;
		if(a[k].c>0  &&  d[y]==d[x]-a[k].d  &&  v[y]==true  &&  ans<f)
		{
			ans+=t=find(y,mymin(a[k].c,f-ans));
			a[k].c-=t;a[a[k].other].c+=t;cost+=t*a[k].d;
		}
	}
	v[x]=true;
	return  ans;
}
int  main()
{
	scanf("%d",&n);st=0;ed=n+1;
	for(int  i=1;i<=n;i++)
	{
		int  x;scanf("%d",&x);
		int  l=i-1,r=i+1;
		if(l==0)l=n;/*环特判*/
		if(r==n+1)r=1;/*环特判*/
		ins(i,l,999999999,1);ins(i,r,999999999,1);ins(st,i,x,0);
		sum+=x;
	}
	sum/=n;/*总和*/
	for(int  i=1;i<=n;i++)ins(i,ed,sum,0);/*连边*/
	int  ans=0;
	memset(v,true,sizeof(v));n+=2;
	while(spfa())find(st,999999999);/*ZKW费用流*/
	printf("%d\n",cost);/*输出*/
	return  0;
}