#include <bits/stdc++.h>
using namespace std;
const long long inf=1e16;
int n,a[510],vis[510];
long long f[510][510],g[510];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int t=1;t<n;t++){
		for(int l=1,r=l+t;r<=n;l++,r++){
			g[l]=inf;vis[l]=0;
			for(int i=l/2+1;i<=r/2;i++) g[l]=min(g[l],max(f[1][2*i-l],f[i*2][r])+a[i]);
			for(int i=(n+l)/2+1;i<=(n+r)/2;i++) g[l]=min(g[l],max(f[l][2*i-n-1],f[2*i-r][n])+a[i]);
		}
		for(int i=1;i+t<=n;i++){
			int k=0,r;
			for(int l=1;l+t<=n;l++){
				if((k==0||g[l]<g[k])&&!vis[l]) k=l;
			}
			vis[k]=1;r=k+t;//cout<<k<<endl;
			for(int j=r/2+1;j<=(n+k)/2;j++) g[j*2-r]=min(g[j*2-r],g[k]+a[j]);
		}
		for(int i=1;i+t<=n;i++) f[i][i+t]=g[i];
	}
	cout<<f[1][n];
	return 0;
}