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

int main(){
   cin>>N;
   int b,m;
   for(int i=1;i<=N;i++)
      cin>>A[i];
   for(int a=1;a<=N;a++) {K[a][a]=0; F[a][a]=A[a];}
   for(int a=1;a<N;a++){
      K[a][a+1]=min(A[a],A[a+1]);
      F[a][a+1]=max(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;
         F[a][b]=max(F[a][b-1],A[b]);
         for(int u=a;u<b;u++){
            m=max(K[a][u],K[u+1][b])+min(F[a][u],F[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])+F[u+1][v];     //ternáris eset
               K[a][b]=min(K[a][b],m);
            }
         }
      }
   }
   cout<<K[1][N]<<endl;
}