#include<stdio.h>
#define max( x , y ) ( x < y ? y : x )
#define Nmax 101

long a[Nmax];
long c[Nmax][Nmax];

int main()
{

int n,i,j,k;

freopen("reduceri.in","r",stdin);
freopen("reduceri.out","w",stdout);

scanf("%d",&n);

for(i=1;i<=n;i++)
 scanf("%ld",a+i);


  for(i=1;i<=n;i++)
   c[i][i]=a[i];


   for ( j=1 ; j < n ; j ++ )
    for ( i=1 ; i < n-j+1 ; i++ )
     {
       c[i][i+j]= max( a[i+j]-a[i], a[i]-a[i+j] )*(j+1);
     for ( k=i; k <= i+j-1; k ++ )
      c[i][i+j]= max( c[i][i+j], c[i][k]+c[k+1][i+j]);
     }


  printf("%ld\n", c[1][n]);

  return 0;
  }