#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5e5+1, inf = LLONG_MAX;
int n, a[N], pre[N];
vector<pair<int, int>> dp[N];
signed main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
a[0] = pre[0] = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = a[i] + pre[i-1];
}
dp[0].push_back(make_pair(0, 0));
for (int i = 0; i < n; i++) {
pair<int, int> p = make_pair(-inf, inf);
for (auto& [x, y] : dp[i]) {
if (x > p.first) {
assert(y <= p.second);
p = make_pair(x, y);
}
else if (x == p.first) {
p.second = min(p.second, y);
}
}
// no hago grupo nuevo
dp[i+1].push_back(make_pair(p.first, p.second + a[i+1]));
// hago grupo nuevo
int l = i+1;
int r = n+1;
while (l < r) {
int mid = (l+r)/2;
int x = pre[mid] - pre[i];
if (x >= p.second) r = mid;
else l = mid+1;
}
if (r == n+1) continue; // cogiendo todos sigue siendo menor
dp[l].push_back(make_pair(p.first+1, pre[l] - pre[i]));
}
int ans = -inf;
for (auto& [x, y] : dp[n]) {
ans = max(ans, x);
}
cout << ans << "\n";
}
