#include <bits/stdc++.h>
using namespace std;
using ll = long long;
// Fenwick tree for range‐maximum queries
struct Fenwick {
int n;
vector<int> f;
Fenwick(int _n): n(_n), f(n+1, 0) {}
// point update: set f[i] = max(f[i], v)
void update(int i, int v) {
for(; i <= n; i += i & -i)
f[i] = max(f[i], v);
}
// prefix query: max over f[1..i]
int query(int i) const {
int r = 0;
for(; i > 0; i -= i & -i)
r = max(r, f[i]);
return r;
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N;
cin >> N;
vector<ll> a(N), S(N+1, 0);
for(int i = 0; i < N; i++){
cin >> a[i];
S[i+1] = S[i] + a[i];
}
// 1) coordinate‐compress all prefix‐sums S[0..N]
vector<ll> all = S;
sort(all.begin(), all.end());
all.erase(unique(all.begin(), all.end()), all.end());
auto idx = [&](ll x){
return int(lower_bound(all.begin(), all.end(), x) - all.begin()) + 1;
};
// 2) bestSum[d] = minimum prefix‐sum S[j] at which we can form d segments
vector<ll> bestSum(N+2, LLONG_MAX);
bestSum[0] = 0;
// 3) Fenwick tree will store, for each “key” K_j = 2*S[j] - bestSum[d_j], the value d_j
// so that querying up to S[i] gives the max d_j with K_j <= S[i].
// Because K_j may not be in our compressed array, we’ll separately compress the set of
// all possible keys as we go, by inserting (2*S[j] - bestSum[d_j]) into a second list.
//
// But we can avoid a second compression if we notice that:
// K_j <= S[i]
// ⇔ 2*S[j] - bestSum[d_j] <= S[i]
// ⇔ S[j] <= (S[i] + bestSum[d_j]) / 2
//
// However, that mixes d_j inside the bound, so we still need the original trick.
//
// For clarity and speed in contest, here’s the standard two‐Fenwick approach:
// Prepare to collect all keys
vector<ll> keys;
keys.reserve(N+1);
// initial j=0: d_j=0, bestSum[0]=0 -> key = 2*S[0] - 0 = 0
keys.push_back(0);
for(int j = 1; j <= N; j++){
// we’ll later fill in key for each j once we know d_j
// but for size we can push a placeholder
keys.push_back(0);
}
// we will fill keys[j] = 2*S[j] - bestSum[d_j] after we compute d_j,
// so let's do that on the fly, but we need the Fenwick size upfront:
// to be safe, we’ll just compress over the union of all S[] and all (2*S[j]-anything),
// but that’s tricky. Instead, we’ll do this:
// — first pass: assume d_j <= N, bestSum[d_j] <= max S, so key <= 2*maxS.
// — we can compress the range [minKey..maxKey] by noticing it’s still O(N).
//
// Actually the simplest is: we know every time we update bestSum[d+1] = S[i], the
// corresponding key = 2*S[i] - bestSum[d] is ≥ S[i] (since bestSum[d] ≤ S[i]).
// So all keys we ever produce lie in [min S .. 2*max S].
// We can collect them in a vector during the loop, then rebuild Fenwick.
// Instead, let's do two‐pass:
// Pass 1: compute dp_i and bestSum, collect keys.
// Pass 2: compress keys and replay updates into Fenwick to answer.
// PASS 1: compute dp_i and bestSum, collect raw key values
vector<int> dp(N+1, 0);
for(int i = 1; i <= N; i++){
// find best d with bestSum[d] <= S[i] by binary search
int lo = 0, hi = i;
while(lo < hi){
int mid = (lo + hi + 1) >> 1;
if(bestSum[mid] <= S[i]) lo = mid;
else hi = mid - 1;
}
dp[i] = lo;
// update bestSum for d+1
bestSum[lo+1] = min(bestSum[lo+1], S[i]);
// record the key for this j=i
ll key = 2*S[i] - bestSum[lo];
keys[i] = key;
}
// Now compress all unique key values alongside S[i]
vector<ll> allKeys = keys;
sort(allKeys.begin(), allKeys.end());
allKeys.erase(unique(allKeys.begin(), allKeys.end()), allKeys.end());
auto keyIdx = [&](ll x){
return int(lower_bound(allKeys.begin(), allKeys.end(), x) - allKeys.begin()) + 1;
};
// Build Fenwick over key‐indices
Fenwick fenw((int)allKeys.size());
// Re‐initialize bestSum & answer, then replay
fill(bestSum.begin(), bestSum.end(), LLONG_MAX);
bestSum[0] = 0;
int answer = 0;
// j=0 initial state
fenw.update(keyIdx(0), 0);
for(int i = 1; i <= N; i++){
// dp_i is exactly the best we can get by querying all keys ≤ S[i]
// i.e. find the last key-value index such that key ≤ S[i]
int pos = int(upper_bound(allKeys.begin(), allKeys.end(), S[i]) - allKeys.begin());
int bestd = fenw.query(pos);
answer = max(answer, bestd);
// now update for j=i: we can form bestd+1 segments ending here
// key = keys[i]
int kpos = keyIdx(keys[i]);
fenw.update(kpos, bestd+1);
}
cout << answer << "\n";
return 0;
}
