var
  n,i:longint;
  a:array[0..10000]of longint;
  f:array[0..1000,0..1000]of longint;

function max(x,y:longint):longint;
begin
  if x>y then exit(x);
  exit(y);
end;

function deal(i,j:longint):longint;
begin
  deal:=(j-i+1)*abs(a[i]-a[j]);
end;

function go(i,j:longint):longint;
var
  k,now:longint;
begin
  if i>j then exit(0);
  if f[i,j]>0 then exit(f[i,j]);

  now:=-maxlongint;
  for k:=i to j do
  now:=max(now,deal(i,k)+go(k+1,j));

  for k:=i to j do
  now:=max(now,go(i,k-1)+deal(k,j));

  for k:=i to j-1 do
  now:=max(now,go(i,k)+go(k+1,j));

  f[i,j]:=now;
  go:=now;
end;

begin
  assign(input,'remove.in'); reset(input);
  assign(output,'remove.out'); rewrite(output);
  readln(n);
  for i:=1 to n do
  begin
    read(a[i]);
    f[i,i]:=a[i];
  end;
  writeln(go(1,n));
  close(input);
  close(output);
end.