#include<iostream>
#include<fstream>
#include<cstdlib>

using namespace std;

int f[1000][1000],a[1000],n;

int main()
{
	int i,j,k,l;
	ifstream fin("remove.in");
	ofstream fout("remove.out");
	fin>>n;
	for(i=1;i<=n;i++) 
	{
		fin>>a[i];
		f[i][i]=a[i];
    }
	for(i=1;i<n;i++)
		for (j=1;j<n;j++)
		{
			k=i+j;
			if(k>n) 
				continue;
			f[j][k]=abs(a[k]-a[j])*(k-j+1);
			for(l=j;l<k;l++)
				if(f[j][l]+f[l+1][k]>f[j][k])
					f[j][k]=f[j][l]+f[l+1][k];
		}	
	fout<<f[1][n];
	return 0;
}