#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 302;

int f[MAXN], dp[MAXN][MAXN], opt[MAXN][MAXN];

void solve() {
    int n; cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> f[i];
    }

    for (int i = 1; i <= n; i++) {
        opt[i][i] = i;
        for (int j = 1; j <= n; j++) {
            if (i >= j) dp[i][j] = 0;
            else dp[i][j] = 1e9;
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = i+1; j <= n; j++) {
            for (int z = max(i, opt[i][j-1]-20); z <= j; z++) {
                int maxe = 0;
                for (int y = z; y <= j; y++) {
                    maxe = max(maxe, f[y]);
                    // if (i == 1 && j == 7) cerr << z << " " << y << " " << dp[i][z-1] << " " << dp[z][y] << " " << dp[y+1][j] << " " << get_max(z, y) << endl;
                    ll val = max(dp[i][z-1], max(dp[z][y], dp[y+1][j])) + maxe;
                    if (dp[i][j] > val) {
                        dp[i][j] = val;
                        opt[i][j] = z;
                    }
                }
            }
        }
    }
    /*cerr << opt[1][8] << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cerr << dp[i][j] << " ";
        }
        cerr << endl;
    }*/
    cout << dp[1][n] << "\n";
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}