#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],dp[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]+min(b[i],b[i-1]);
		for(int i=1;i<=n;++i) fill(dp[i]+1,dp[i]+n+1,1e18);dp[1][1]=0;
		for(int i=1;i<=n;++i)
		{
			for(int j=i;j<=n;++j)
			{
				if(i<j) W(dp[i+1][j],dp[i][j]+b[i]);
				if(j<n) W(dp[i][j+1],dp[i][j]+b[j]);
			}
			for(int j=n,t=n;j>i;--j)
			{
				if(j<n) W(dp[i][j],dp[i][j+1]);while(t && a[t]>a[j]*2-a[i]) --t;
				W(dp[j][t],dp[i][j]+sqr(a[i]-a[j])+s[j-1]-s[i]);
				if(t<n) W(dp[j][t+1],dp[i][j]+sqr(a[j]-a[t+1])+s[j-1]-s[i]);
			}
		}printf("%lld\n",dp[n][n]);
	}return 0;
}