C++ :

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn = 1000000+5;

long long A[maxn],C[maxn],tot,avg;	

int main()
{
	//freopen("1.txt","r",stdin);
	//freopen("2.txt","w",stdout);
	
	int n;
	while(cin >> n) {
//	while(scanf("%d",&n) == 1) {
		tot = 0;
		for(int i = 1; i <= n; i++) {
			cin >> A[i];
		//	scanf("%lld", &A[i]);
			tot += A[i];
		}
		
		avg = tot / n;
		C[0] = 0;
		for(int i = 1; i < n; i++) {
			C[i] = C[i-1] + A[i] - avg;
		}
		
		sort(C,C+n);
		
		long long x1 = C[n/2], ans = 0;
		for(int i = 0; i < n; i++) {
			ans += abs(x1-C[i]);
		}
		
		//printf("%lld\n", ans);		
		cout << ans << endl;
	}	
	
	return 0;
}