program remove;
var
  i,j,k,k1,k2,n:longint;
  f,w:array[0..100,0..100]of longint;
  a:array[1..100]of longint;
procedure init;
begin
  assign(input,'remove.in');
  reset(input);
  assign(output,'remove.out');
  rewrite(output);
  read(n);
  for i:=1 to n do
    read(a[i]);
  for i:=1 to n do
    f[i,1]:=a[i];
  for i:=1 to n do
    for j:=1 to n do
      if i<=j then
      begin
        w[i,j]:=abs(a[i]-a[j])*(j-i+1);
        if i=j then
          w[i,j]:=a[i]
      end
end;

procedure dp;
begin
  for j:=1 to n do
    for i:=1 to n do
      if i+j-1<=n then
      begin
        f[i,j]:=w[i,i+j-1];
        for k:=i to i+j-1 do
          if f[i,j]<f[i,k-i+1]+f[k+1,j-(k-i+1)] then
            f[i,j]:=f[i,k-i+1]+f[k+1,j-(k-i+1)]
      end
end;

procedure print;
begin
  writeln(f[1,n]);
  close(input);
  close(output)
end;

begin
  init;
  dp;
  print
end.