#include<bits/stdc++.h> using namespace std; int n; int a[1000005]; int dp[5005][5005]; int mx[5005][5005]; signed main(){ freopen("legion.in","r",stdin); freopen("legion.out","w",stdout); scanf("%d",&n); for(int i = 1;i<=n;i++)scanf("%d",&a[i]); for(int l = 1;l<=n;l++){ for(int i = 1;i<=n;i++){ int j = i+l-1; if(j>n)continue; mx[i][j]=max(mx[i][j-1],a[j]); if(j==i)continue; dp[i][j]=min(dp[i][j-1],dp[i+1][j])+mx[i][j]; } } cout<<dp[1][n]<<endl; //fclose(stdin); //fclose(stdout); } //O(n^2);