#include <bits/stdc++.h>
using namespace std;
int fun(int n, vector<int>&p) {
	int sum=0;
	for(int i=0; i<n; i++) {
		sum+=p[i];
	}
	int temp=sum/n;
	queue<pair<int,int>>q;
	int s=true;
	int cost=0;
	for(int i=0; i<n; i++) {

		if(p[i]>temp) {
			q.push({p[i]-temp,i});
		}
		else if(p[i]<temp && !q.empty()) {
			while(!q.empty() && p[i]!=temp) {
				auto a=q.front();
				q.pop();
				if(temp-p[i]<a.first) {
					a.first-=(temp-p[i]);
					if(s)
					{
						cost+=(temp-p[i])*(i-a.second);
					}
					else {
						cost+=(temp-p[i])*(n-1-a.second + 1 + i);
					}
					p[i]=temp;
					q.push(a);
				}
				else {
					if(s)
					{
						cost+=(a.first*(i-a.second));
					}
					else {
						cost+=(a.first)*(n-1-a.second + 1 + i);
					}

					p[i]=p[i]+a.first;
				}
			}
		}
		if(s && i==n-1 && !q.empty()) {
			i=-1;
			s=false;
		}
	}
	return cost;
}
int main()
{
	int n;
	cin>>n;
	vector<int>r,p(n);
	for(int i=0; i<n; i++) {
		cin>>p[i];
	}
	r=p;
	reverse(r.begin(),r.end());
	cout<<min(fun(n,p),fun(n,r))<<endl;
	return 0;
}