#include<fstream>
using namespace std;
ifstream cin("remove.in");
ofstream cout("remove.out");
int n,x,i,j,p,f[1000][1000],a[1000];
int jue(int a)
{
	if(a>=0)
		return a;
	else
		return -a;
}
int main()
{
	cin>>n;
	for(i=1;i<=n;i++) 
	{
		cin>>a[i];
		f[i][i]=a[i];
	}
	for (i=1;i<n;i++)
		for (j=1;j<n;j++)
		{
			p=i+j;
			f[j][p]=jue(a[p]-a[j])*(p-j+1);
			for(x=j;x<p;x++)
				if (f[j][x]+f[x+1][p]>f[j][p])
					f[j][p]=f[j][x]+f[x+1][p];
		}
	cout<<f[1][n]<<endl;
	return 0;
}