#include <bits/stdc++.h>
#define maxN 301
#define Infi 10000000
using namespace std;
int N;
int A[maxN]; int F[maxN];
int K[maxN][maxN];

int Keres(int a, int b, int i, int j){
//Global:A,F
//a<=i<=j<=b [a,b] elõszámított intervallum, értéke F[(a+b)/2]
  if(i==j)
    return A[i];
  int k=(a+b)/2;
  if(a==i && b==j)
    return F[k];
  if(j<=k) return Keres(a,k,i,j);
  if(k<i) return Keres(k+1,b,i,j);
  return max(Keres(a,k,i,k), Keres(k+1,b,k+1,j));
}
int Kezd(int a, int b){
//Global:A,F
  if(a==b)
    return A[a];
  else{
    int k=(a+b)/2;
    F[k]=max(Kezd(a,k), Kezd(k+1,b));
    return F[k];
  }
}

int main(){
   cin>>N;
   int b,m;
   for(int i=1;i<=N;i++)
      cin>>A[i];
   Kezd(1,N);
   for(int a=1;a<=N;a++) K[a][a]=0;
   for(int a=1;a<N;a++)
      K[a][a+1]=min(A[a],A[a+1]);
   for(int d=2;d<N;d++){
      for(int a=1;a+d<=N;a++){
         b=a+d;
         K[a][b]=Infi;
         for(int u=a;u<b;u++){
            m=max(K[a][u],K[u+1][b])+min(Keres(1,N,a,u),Keres(1,N,u+1,b)); //bináris eset
            K[a][b]=min(K[a][b],m);
            for(int v=u+1;v<b;v++){//a<=u<=v<=b
               m=max(max(K[a][u],K[u+1][v]),K[v+1][b])+Keres(1,N,u+1,v);     //ternáris eset
               K[a][b]=min(K[a][b],m);
            }
         }
      }
   }
   cout<<K[1][N]<<endl;
}