#include<bits/stdc++.h>
using namespace std;
#define int long long
const int NR=3010;
int n,a[NR],f1[NR][NR],f2[NR][NR],sum[NR];
void chkmin(int &x,int y){x=(x<y)?x:y;}
int sq(int x){return x*x;}

signed main(){
	while(cin>>n){
		for(int i=1;i<=n;i++)cin>>a[i];
		for(int i=1;i<=n;i++)sum[i]=sum[i-1]+sq(a[i]-a[i-1]);
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				f1[i][j]=f2[i][j]=1e18;
		f1[1][1]=f2[1][1]=0;
		for(int i=1;i<=n;i++){
			for(int j=n-1;j>=i;j--)chkmin(f2[i][j],f2[i][j+1]);
			for(int j=i;j<=n;j++){
				if(i<j)chkmin(f1[i][j],f2[i][j]+sum[j-1]-sum[i]);
				if(j<n)chkmin(f1[i][j+1],f1[i][j]+sq(a[j+1]-a[j]));
				if(i<j)chkmin(f2[i+1][j],f2[i][j]+sq(a[i+1]-a[i]));
			}
			for(int j=n,now=n;j>i;j--){
				while(now&&a[now]>a[j]*2-a[i])now--;
				chkmin(f2[j][now],f1[i][j]+sq(a[j]-a[i]));
				if(now<n)chkmin(f2[j][now+1],f1[i][j]+sq(a[now+1]-a[j]));
			}
		}
		cout<<f2[n][n]<<endl;
	}
	return 0;
}