#include <bits/stdc++.h>
 
using namespace std;

template<ranges::range T, class = enable_if_t<!is_convertible_v<T, string_view>>>
istream& operator>>(istream &s, T &&v) { for (auto &&x : v) s >> x; return s; }
template<ranges::range T, class = enable_if_t<!is_convertible_v<T, string_view>>>
ostream& operator<<(ostream &s, T &&v) { for (auto &&x : v) s << x << ' '; return s; }
 
#ifdef LOCAL
template<class... T> void dbg(T... x) { char e{}; ((cerr << e << x, e = ' '), ...); }
#define debug(x...) dbg(#x, '=', x, '\n')
#else
#define debug(...) ((void)0)
#endif
 
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define ff first
#define ss second
 
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128;
using u128 = unsigned __int128;
using Pt = pair<double, double>;
 
template<class T> inline constexpr T inf = numeric_limits<T>::max() / 2;
constexpr int mod = 1e9 + 7, inv2 = (mod + 1) / 2;
constexpr double eps = 1e-9;
 
template<class T> bool chmin(T &a, T b) { return (b < a and (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b and (a = b, true)); }

void solve() {
    int n;
    cin >> n;

    vector<i64> A(n);
    cin >> A;

    vector<i64> dp(n);
    dp[0] = A[0];
    
    partial_sum(all(A), A.begin());

    vector<pair<i64, int>> stk{pair(dp[0] + A[0], 0)};
    for (int i = 1; i < n; i++) {
        dp[i] = A[i];
        
        auto it = upper_bound(all(stk), pair{A[i], -1});
        if (it != stk.begin()) {
            it--;
            chmin(dp[i], A[i] - A[it->ss]);
        }

        while (stk.size() and stk.back().ff >= dp[i] + A[i]) {
            stk.pop_back();
        }
        stk.emplace_back(dp[i] + A[i], i);
    }

    i64 ans = dp[n - 1];
    for (int i = 0; i < n; i++) {
        chmin(ans, max(dp[i], A[n - 1] - A[i]));
    }

    cout << ans << '\n';
}
 
signed main() {
    cin.tie(0)->sync_with_stdio(false);
    cin.exceptions(cin.failbit);
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}