#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=3e3+5;
int n,a[N];ll b[N],s[N],dp1[N][N],dp2[N][N];
void W(ll &x,ll y) {x=min(x,y);}
ll sqr(int x) {return 1ll*x*x;}
int main()
{
	while(~scanf("%d",&n))
	{
		for(int i=1;i<=n;++i) scanf("%d",&a[i]);
		b[0]=b[n]=1e18;for(int i=1;i<n;++i) b[i]=sqr(a[i]-a[i+1]);
		for(int i=1;i<=n;++i) s[i]=s[i-1]+b[i-1];
		for(int i=1;i<=n;++i) for(int j=i;j<=n;++j) 
			dp1[i][j]=dp2[i][j]=1e18;dp1[1][1]=dp2[1][1]=0;
		for(int i=1;i<=n;++i)
		{
			for(int j=n-1;j>=i;--j) W(dp2[i][j],dp2[i][j+1]);	
			for(int j=i;j<=n;++j)
			{
				if(i<j) W(dp1[i][j],dp2[i][j]+s[j-1]-s[i]);
				if(j<n) W(dp1[i][j+1],dp1[i][j]+b[j]);
				if(i<j) W(dp2[i+1][j],dp2[i][j]+b[i]);
			}
			for(int j=n,t=n;j>i;--j)
			{
				while(t && a[t]>a[j]*2-a[i]) --t;
				W(dp2[j][t],dp1[i][j]+sqr(a[i]-a[j]));
				if(t<n) W(dp2[j][t+1],dp1[i][j]+sqr(a[j]-a[t+1]));
			}
		}printf("%lld\n",dp2[n][n]);
	}return 0;
}