#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#define int long long
#define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

using namespace std;

const int MAXN = 2005;

int n;
int a[MAXN];
int pref[MAXN];
int val[MAXN][MAXN];

inline int getSum(int l, int r){
    return pref[r] - pref[l - 1];
}

signed main() {
    itachi

    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i];
        val[i][i] = a[i];
    }

    for(int len = 2; len <= n; len++){
        for(int l = 1; l + len - 1 <= n; l++){
            int r = l + len - 1;

            int lo = l, hi = r - 1;
            while(lo < hi){
                int mid = (lo + hi) >> 1;
                if(val[l][mid] < val[mid + 1][r]) lo = mid + 1;
                else hi = mid;
            }

            int best = -1;
            for(int m = max(l, lo - 1); m <= min(r - 1, lo); m++){
                best = max(best, min(val[l][m], val[m + 1][r]));
            }

            val[l][r] = getSum(l, r) + best;
        }
    }

    cout << val[1][n] - getSum(1, n) << '\n';
    return 0;
}