#define _XOPEN_SOURCE 500
#include <bits/stdc++.h>

#define rep(i, n) for (int i = 0; i < (n); ++i)
#define reps(i, n) for (int i = 1; i <= (n); ++i)
#define repd(i, n) for (int i = (n - 1); i >= 0; --i)
#define repds(i, n) for (int i = (n); i > 0; --i)
#define loop(i, x, n) for (int i = (x); i < (n); ++i)
#define loops(i, x, n) for (int i = (x); i <= (n); ++i)
#define loopd(i, x, n) for (int i = (x); i > (n); --i)
#define loopds(i, x, n) for (int i = (x); i >= (n); --i)
#define itrep(i, a) for (auto i = begin(a); i != end(a); ++i)
#define itrepd(i, a) for (auto i = rbegin(a); i != rend(a); ++i)
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using ld = long double;
template <class T>
using priority_queuel = priority_queue<T, vector<T>, greater<T>>;
constexpr ll inf = static_cast<ll>(1e18);
constexpr int iinf = static_cast<int>(1e9);
constexpr double dinf = 1e10;
constexpr ld ldinf = 1e18;
constexpr double eps = 1e-9;
ll mod = static_cast<ll>(1e9 + 7);
template <class T>
constexpr int sz(const T &a) { return (int)a.size(); }
template <class T>
constexpr T pow2(const T a) { return a * a; }
template <class T, class... Args>
constexpr void mins(T &a, Args... args) { a = min<T>({a, args...}); }
template <class T, class... Args>
constexpr void maxs(T &a, Args... args) { a = max<T>({a, args...}); }
template <class A, int N, class T>
void fillArray(A (&array)[N], const T &val) { std::fill((T *)array, (T *)(array + N), val); }

template <class T>
class SegmentTree2 {
public:
    SegmentTree2(int n_, T init, T limit_, std::function<T(T, T)> comp_) : n(1), limit(limit_), comp(comp_) {
        while (n < n_)
            n *= 2;
        d.resize(2 * n - 1, init);
        v.resize(2 * n - 1, 0);
    }
    // d[[a,b)]+=x
    void add(int a, int b, T x, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        eval(k, l, r);
        if (r <= a || b <= l) return;
        if (a <= l && r <= b) {
            v[k] += x;
            eval(k, l, r);
        } else {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            d[k] = comp(d[2 * k + 1], d[2 * k + 2]);
        }
    }
    // comp() [a,b)
    T query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (r <= a || b <= l) return limit;
        eval(k, l, r);
        if (a <= l && r <= b) return d[k];
        T vl = query(a, b, 2 * k + 1, l, (l + r) >> 1);
        T vr = query(a, b, 2 * k + 2, (l + r) >> 1, r);
        return comp(vl, vr);
    }

private:
    void eval(int k, int l, int r) {
        if (v[k] != 0) {
            d[k] += v[k];
            if (r - l > 1) {
                v[2 * k + 1] += v[k];
                v[2 * k + 2] += v[k];
            }
            v[k] = 0;
        }
    }
    int n;
    const T limit;
    std::function<T(T, T)> comp;
    vector<T> d, v;
};

int n;
ll a[2005];
ll dp[4005];
void solve() {
    cin >> n;
    rep(i, n) cin >> a[i];

    rep(i, n) {
        SegmentTree2<ll> st(2 * n + 2, 0, -inf, [](auto x, auto y) { return max(x, y); });
        auto r = max(i, n - i - 1);
        reps(j, 2 * n) {
            st.add(max(0, j - r), j, a[i]);
            st.add(j, j + 1, dp[j]);
            auto val = st.query(0, j + 1);
            dp[j] = val;
        }
    }
    cout << dp[2 * n - 1] << endl;
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    solve();
    return 0;
}
