#include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; const int N = 5e5 + 5; int a[N], pr[N], cur[N], dp[N][2], st[N * 4], n; void upd(int v, int l, int r, int pos, int val){ if(l == r){ st[v] = val; return; } int mid = (l + r) >> 1; if(mid >= pos)upd(v * 2, l, mid, pos, val); else upd(v * 2 + 1, mid + 1, r, pos, val); st[v] = min(st[v * 2], st[v * 2 + 1]); } int ask(int v, int l, int r, int ql, int qr){ if(l > qr || r < ql)return INF; if(l >= ql && r <= qr)return st[v]; int mid = (l + r) >> 1; return min(ask(v * 2, l, mid, ql, qr), ask(v * 2 + 1, mid + 1, r, ql, qr)); } int get(int l, int r){ return ask(1, 1, n, l, r); } int Best(int v, int tl, int tr, int x){ if (tl == tr)return tl; int mid = (tl + tr) >> 1; if(st[v * 2 + 1] <= x){ return Best(v * 2 + 1, mid + 1, tr, x); } else if (st[v * 2] <= x){ return Best(v * 2, tl, mid, x); } return 0; } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for(int i = 1; i <= n; i++){ cin >> a[i]; pr[i] = pr[i - 1] + a[i]; dp[i][0] = -1; dp[i][1] = INF; upd(1, 1, n, i, INF); } dp[1][0] = 1; dp[1][1] = a[1]; upd(1, 1, n, 1, a[1] + pr[1]); for(int i = 2; i <= n; i++){ int best = Best(1, 1, n, pr[i]); dp[i][1] = min(dp[i][1], pr[i] - pr[best]); upd(1, 1, n, i, dp[i][1] + pr[i]); dp[i][0] = dp[best][0] + 1; } cout << dp[n][0] << endl; }