1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath> 
 4 
 5 using namespace std;
 6 
 7 int n,a[101],f[101][101]; 
 8 
 9 inline int max(int s,int d) {
10     if(s > d) return s;
11     return d;
12 }
13 
14 int main() {
15     scanf("%d",&n);
16     for(int i = 1;i <= n; i++) {
17         scanf("%d",&a[i]);
18         f[i][i] = a[i];
19     }
20     for(int len = 1;len < n; len++)
21         for(int i = 1,j = i + len;j <= n; i++,j++) {
22             f[i][j] = abs(a[i] - a[j]) * (j - i + 1);
23             for(int k = i;k < j; k++)
24                 f[i][j] = max(f[i][j],f[i][k] + f[k+1][j]);
25         }
26     printf("%d",f[1][n]);
27     return 0;
28 }