/* Telebe of Adicto && Mamedov yani AzeTurk810 I see humans but no humanity Music: https://www.youtube.com/watch?v=Qrgnr0N8iwU&list=RDGMEMQ1dJ7wXfLlqCjwV0xfSNbA&start_radio=1&rv=KlKheV-r8oo, https://www.youtube.com/watch?v=mewNjPCi76E&list=RDmewNjPCi76E&start_radio=1 */ #include <algorithm> #include <iostream> #include <map> #include <utility> #include <vector> // mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); using ll = long long; using namespace std; #define ln '\n' #define INFi 1e9 #define INFll 1e18 #ifdef ONPC #include <algo.hpp> #else #define dbg(...) #define dbg_out(...) #endif #define int ll char solve() { int N; if (!(cin >> N)) return 1; vector<int> A(N + 1); vector<pair<int, int>> dp(N + 1); for (int i = 1; i <= N; i++) { cin >> A[i]; dp[i] = {1, 0}; } vector<vector<int>> sums(N + 1); vector<int> pref(N + 1); for (int i = 1; i <= N; i++) { pref[i] = pref[i - 1] + A[i]; } for (int i = 1; i <= N; i++) { dp[i] = max(dp[i - 1], dp[i]); auto it = lower_bound(pref.begin(), pref.end(), 2 * pref[i] - (pref[dp[i].second])); if (it == pref.end()) continue; int j = it - pref.begin(); dp[j] = max(dp[j], {dp[i].first + 1, i}); } cout << dp.back().first << ln; return 0; } // Attack on titan<3 signed main() { ios::sync_with_stdio(0); cin.tie(nullptr); int t = 1e9; // cin >> t; for (int cases = 0; cases < t; cases++) { if (solve()) break; #ifdef ONPC cerr << "__________\n"; #endif } } // Just Imaginary /* ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢀⣀⣀⠀⠀⠀⢀⣴⣾⠀⠀⠀⡀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⢸⣿⣿⣿⣦⣾⣿⣿⣿⣿⣿⡆⠁⠀⢀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠹⣿⣿⣿⣿⣿⣿⣿⣿⡿⠁⠀⡠⠂⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⣀⠠⠔⠚⣿⣿⣿⣿⣿⣦⡄⠀⠁⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⢀⠠⠐⢂⠉⡀⣀⣤⣄⢻⣿⣿⡟⢈⡹⣿⡀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⡀⠄⠂⠈⠀⣶⣤⣾⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⠘⣷⡀⠀⡀⠐⠂⠐⢄ ⠀⠀⠀⠀⠀⠀⠀⣿⣿⠟⠿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣧⣀⣾⣷⠯⠀⠤⠤⠄⠈ ⠀⠀⠀⠀⠀⠀⣼⣿⡟⠀⠀⣹⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣿⣷⣄⡀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⣰⣿⠋⠀⠀⢠⣾⣿⣿⣿⣿⣿⣭⠟⢻⣿⣿⣿⣿⡿⠁⠀⠀⠀⠀ ⠀⠀⠀⣀⣶⡟⠁⠀⢾⣶⣿⠟⠉⠈⢻⣿⣿⣿⣦⣜⠀⠛⠛⠿⠁⠀⠀⠀⠀⠀ ⠚⠻⠿⠿⡿⠁⠀⢠⣿⣿⠁⠀⣠⠖⠋⠉⠻⣿⣿⣿⣶⡀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⠀⠀⣰⣿⡿⠃⠠⠊⠁⠀⠀⠀⠀⠈⢿⣿⣿⠟⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⠀⢀⣴⡿⠋⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠘⠁⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⠀⠀⠀⣠⣾⠏⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ ⢀⣴⠾⠟⠛⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀⠀ */