#include <bits/stdc++.h>

using ll = long long;
using namespace std;

const int MAXN = 302;

int f[MAXN], dp[MAXN][MAXN], bef[MAXN], aft[MAXN];

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

    stack<int> mt;
    for (int i = 1; i <= n; i++) {
        while (!mt.empty() && f[mt.top()] < f[i]) mt.pop();
        bef[i] = mt.empty() ? 1 : mt.top();
        mt.push(i);
    }
    mt = stack<int>();
    for (int i = n; i >= 1; i--) {
        while (!mt.empty() && f[mt.top()] < f[i]) mt.pop();
        aft[i] = mt.empty() ? n : mt.top();
        mt.push(i);
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i > j) dp[i][j] = 0;
            else if (i == j) dp[i][j] = f[i];
            else dp[i][j] = 1e9;
        }
    }
    for (int i = n; i >= 1; i--) {
        for (int j = i+1; j <= n; j++) {
            for (int k = i; k <= j; k++) {
                dp[i][j] = min(dp[i][j], dp[i][bef[k]-1] + f[k] + dp[aft[k]+1][j]);
            }
        }
    }
    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;
}