#include <bits/stdc++.h>
using namespace std;
struct segTree {
vector<long long> v, upd;
int sz;
void init(int n){
sz = 1;
while(sz < n) sz *= 2;
v.assign(2 * sz, 1e18);
upd.assign(2 * sz, 0);
}
void set(int l, int r, long long val, int x, int lx, int rx){
if(lx >= l && rx <= r){
if(v[x] == 1e18) v[x] = 0;
v[x] += val;
upd[x] += val;
// cout << "lx " << lx << " rx " << rx <<
return;
}else if(lx >= r || rx <= l) return;
int m = (lx + rx) / 2;
set(l, r, val, 2 * x + 1, lx, m);
set(l, r, val, 2 * x + 2, m, rx);
v[x] = min(v[2 * x + 1], v[2 * x + 2]) + upd[x];
}
void set(int l, int r, long long val){
set(l, r, val, 0, 0, sz);
}
int walk(int x, int lx, int rx, long long curr){
if(rx - lx == 1){
return lx;
}
int m = (lx + rx) / 2;
curr += upd[x];
if(v[2 * x + 2] + curr <= 0) return walk(2 * x + 2, m, rx, curr);
else return walk(2 * x + 1, lx, m, curr);
}
int walk(){
return walk(0, 0, sz, 0);
}
};
long long sum(int l, int r, vector<long long>& prefix){
if(l > r) return 0;
return prefix[r] - prefix[l-1];
}
int solve(int N, vector<int>& a){
vector<long long> prefix(N+1, 0);
for(int i = 1; i <= N; i++){
prefix[i] = prefix[i-1] + a[i];
}
vector<int> ans(N+1);
ans[0] = 0;
segTree st; st.init(N+1);
st.set(0, 1, 0);
for(int i = 1; i <= N; i++){
st.set(0, i, -a[i]);
int ind = st.walk();
ans[i] = ans[ind] + 1;
long long sm = sum(ind + 1, i, prefix);
// cout << "i " << i << " ind " << ind << " sm " << sm << "\n";
st.set(i, i + 1, sm);
}
return ans[N];
}
int brute(int N, vector<int>& a){
int ans = 0;
for(int b = 0; b < (1 << N); b++){
long long lst = 0;
long long sm = 0;
bool gd = true;
int segments = 0;
// cout << "b " << b << "\n";
for(int i = 0; i < N; i++){
sm += a[i+1];
if((1 << i) & b || i == N - 1){
// cout << "i " <<
segments++;
if(lst > sm) gd = false;
lst = sm;
sm = 0;
}
}
if(gd) ans = max(ans, segments);
}
return ans;
}
mt19937 gen(time(0));
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
// string s; cin >> s;
string s = "RUN";
if(s == "RUN"){
int N; cin >> N;
vector<int> a(N+1, 0);
for(int i = 1; i <= N; i++) cin >> a[i];
cout << solve(N, a) << "\n";
return 0;
}
for(int h = 0; h < 1000000; h++){
int n = gen() % 10;
vector<int> a(n+1, 0);
for(int i = 0; i < n; i++){
a[i] = gen() % 10 + 1;
}
int ans1 = solve(n, a);
int ans2 = brute(n, a);
if(ans1 != ans2){
cout << n << "\n";
for(int i = 1; i <= n; i++) cout << a[i] << " ";
cout << "\n";
cout << "Fast ans: " << ans1 << "\n";
cout << "Slow ans: " << ans2 << "\n";
return 0;
}
}
}
