RT

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <functional>
#include <algorithm>
#include <chrono>
#include <random>
using namespace std;

#define int long long

#define double long double

random_device rd;
mt19937_64 mtrand64 {rd()};
uniform_real_distribution<double> disrand(0.0,1.0);
#define rand() disrand(mtrand64)

const double B=1e2L, E=1e-15L, W=0.9999L;

int n,a[10005],cf[10005],s,ssq,nowans=1e18;

int calcans() {
	int ans=0,ans2=0;
	for(int i=1; i<=n; i++) {
		a[i]=a[i-1]+cf[i];
		ans+=a[i];
		ans2+=a[i]*a[i];
	}
	return ans2*n-ans*ans;
}

chrono::nanoseconds BEGIN = chrono::steady_clock::now().time_since_epoch();
void sa(uniform_int_distribution<>& randsel) {
	int x,y;
	for(double j=B; j>E; j*=W) {
		if(chrono::steady_clock::now().time_since_epoch()-BEGIN>=997000000ns) {
			printf("%lld\n",nowans);
			exit(EXIT_SUCCESS);
		}
		do x=randsel(mtrand64),y=randsel(mtrand64);
		while(x==y);
		swap(cf[x],cf[y]);
		int ans=calcans();
		// printf("nowans=%lld\tans=%lld\n",nowans,ans);
		if(nowans>=ans) nowans=ans;
		else if(exp((nowans-ans)*1.0/j)<rand()) swap(cf[x],cf[y]);;
	}
}

signed main() {
	scanf("%lld",&n);
	for(int i=1; i<=n; ++i) scanf("%lld",a+i),cf[i]=a[i]-a[i-1];
	uniform_int_distribution<> randsel(1+1,n-1);
	sort(cf+2,cf+1+n/2,greater<>());
	sort(cf+n/2+1,cf+1+n);
	while(1) sa(randsel);
}