#include <bits/stdc++.h> using namespace std; #define int long long const int INF = 1e18; const int N = 2e5 + 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); } 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 l = 0, r = i; int best = 0; while(r >= l){ int mid = (l + r) >> 1; if(get(mid, i) <= pr[i]){ best = mid; l = mid + 1; } else r = mid - 1; } 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; }