#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5010;
int dp[N][N],a[N],s[N];
signed main()
{
	int n;cin>>n;int sum=0;
	for(int i=1;i<=n;i++)cin>>a[i],sum+=a[i];
	for(int i=n;i>=1;i--)s[i]=s[i+1]+a[i];
	int res=floor(1.0*sum/n),ss=sum-res*n;
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	for(int i=0;i<n;i++)for(int j=0;j<=min(i,ss);j++)
	{
		int sum1=sum-s[i+2]-i*res-j;
		dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+abs(sum1-res-1));
		dp[i+1][j]=min(dp[i+1][j],dp[i][j]+abs(sum1-res));
	}
	cout<<min(dp[n-1][ss],dp[n-1][max(0ll,ss-1)]);
	return 0;
}