#include <bits/stdc++.h> using namespace std; using ll = long long; const ll INF = (ll)9e18; int N; vector<ll> P; bool feasible(int k) { vector<ll> dp_prev(N + 1, INF), dp_curr(N + 1, INF); dp_prev[0] = 0; for (int t = 1; t <= k; ++t) { vector<vector<int>> bucket(N + 1); for (int j = 0; j < N; ++j) { if (dp_prev[j] == INF) continue; ll target = P[j] + dp_prev[j]; auto it = lower_bound(P.begin() + j + 1, P.end(), target); if (it != P.end()) { int pos0 = (int)(it - P.begin()); bucket[pos0].push_back(j); } } priority_queue<ll> pq; for (int i = 1; i <= N; ++i) { for (int j : bucket[i]) { pq.push(P[j]); } if (!pq.empty()) { dp_curr[i] = P[i] - pq.top(); } else { dp_curr[i] = INF; } } dp_prev.swap(dp_curr); fill(dp_curr.begin(), dp_curr.end(), INF); } return dp_prev[N] < INF; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> N; P.assign(N + 1, 0); for (int i = 1; i <= N; ++i) { ll x; cin >> x; P[i] = P[i - 1] + x; } int lo = 1, hi = N, ans = 1; while (lo <= hi) { int mid = (lo + hi) / 2; if (feasible(mid)) { ans = mid; lo = mid + 1; } else { hi = mid - 1; } } cout << ans << '\n'; return 0; }