/** * author: tuncypasha * file: b.cpp * created: 02.02.2026 13:04 * Student of Adicto and Raul2008487 **/ #include <bits/stdc++.h> #define pasha ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); #define int long long #define ff first #define ss second #define pb push_back #define all(v) begin(v), end(v) using namespace std; // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); constexpr int N = 5e5 + 5, K = 26, mod = 1e9 + 7, oo = 1e18; int a[N], pre[N]; array<int, 2> dp[N]; int st[N * 4]; void update(int v, int tl, int tr, int i, int x) { if (tl == tr) { st[v] = x; return; } int tm = (tl + tr) >> 1; if (i <= tm) update(v * 2, tl, tm, i, x); else update(v * 2 + 1, tm + 1, tr, i, x); st[v] = min(st[v * 2], st[v * 2 + 1]); } int find(int v, int tl, int tr, int x) { if (tl == tr) return tl; int tm = (tl + tr) >> 1; if (st[v * 2 + 1] <= x) return find(v * 2 + 1, tm + 1, tr, x); else if (st[v * 2] <= x) return find(v * 2, tl, tm, x); return 0; } void _() { int n; cin >> n; for (int i = 1; i <= n; ++i) { cin >> a[i]; pre[i] = pre[i - 1] + a[i]; dp[i][0] = -1; dp[i][1] = oo; update(1, 1, n, i, oo); } dp[1][0] = 1, dp[1][1] = a[1]; update(1, 1, n, 1, a[1] + pre[1]); for (int i = 2; i <= n; ++i) { int best = find(1, 1, n, pre[i]); dp[i][1] = min(dp[i][1], pre[i] - pre[best]); dp[i][0] = dp[best][0] + 1; update(1, 1, n, i, dp[i][1] + pre[i]); } cout << dp[n][0] << '\n'; } signed main() { pasha int t = 1; // cin >> t; for (int cs = 1; cs <= t; ++cs){ _(); // cout << '\n'; } }