#include <bits/stdc++.h> using namespace std; typedef long long ll; #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #define line() "author : AyazN"; #endif #define all(x) (x).begin(), (x).end() #define isz(x) (int)(x.size()) #define int ll typedef long double ld; typedef pair<int,int> pii; typedef vector<int> vi; typedef vector<vi> vvi; typedef vector<pii> vpii; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int sz = 200500, inf = 1000000000, LOG = 20; const ll mod = 1000000007, INF = 1000000000000000000; void run_case(int tc) { int n; cin >> n; vector<int> a(n + 1), p(n + 1); for (int i = 1; i <= n; i++) { cin >> a[i]; p[i] = p[i - 1] + a[i]; } vector<array<int, 2>> dp(n + 1, {0, 0}); // cnt and sum dp[1] = {1, p[1]}; vector<int> v; for (int i = 2; i <= n; i++) { int cnt = 0, sm = inf; for (int j = 0; j < i; j++) { int sum = p[i] - p[j]; if (sum < dp[j][1]) continue; if (cnt < dp[j][0] + 1) { cnt = dp[j][0] + 1; sm = sum; } else if (cnt == dp[j][0] + 1) { sm = min(sum, sm); } } dp[i] = {cnt, sm}; v.push_back(dp[i][1] + p[i]); } assert(is_sorted(all(v))); cout << dp[n][0] << '\n'; } void precompute() {} signed main() { #ifdef LOCAL // freopen("err.log", "w", stderr); #endif precompute(); int t = 1; // cin >> t; for (int tc = 1; tc <= t; tc++) { run_case(tc); } } /* 0: 0$P: ~~ wPPPI: "~:~ .w$$$PI: . v~++: w$$P$Pcc: ~~ !vv+::~ w$$$P$$cc: ~!~ . cIc::::~+X$$$PP$XIc~~!+" . . ~. vcIo+:!+~w$$$$PP$PIIv~:+~ . . . "v vccI+:++!c$$$$$P$$$II:!+!:.. . .... .. . .. .. .... . .. ......... ....!:!vcIo+++!~wPPPIc:!!+:~ ......... . . .. . ............................."::+coII+!!~"$$$w$$PPIIv!!:: !..............................................!!:v+coIII   +!:cvPPIIv!!::~! .................. ............................!!:v+coIII~~~+!:cvPPIIv!!:: !..............................................!!:v+coIII   +!:cvP$PoIv~!+!+~!................... ............................:!vv~coccv~vvcvcvcwPPPPII:~!:++"+................... ............................++:v"cI::cvvvvv+v:0$PI:  !!:!!!...............................................:c!v:c!ccv::+++!!+0PI:~~!!:!!!................... ............................:c!v:c!ccv::+++!!+0PI:  !!:!!!...............................................:c!v:c!ccv::+++!!+0P:!~~"!!!"++................... ..."....".............~"..+.:vo:vvc:X:!+!!!!!!0P$:++"~!"+~:v!..".....".......... ...."....."........."......++vIcovv:###w!!!!!!w0+!!!"~"~~+!+...".".........."... ."""......."...".$$"."""...!:ccIowv+!#!##!!!!!!!!!!!.~!~~v+"..."..""..........." """""."""""""".""$B"""..."".:wvoco++!o#0R#!!!!!!!!oPPP$":~~""."."""".".""".""."" """".""""""+cc+""..""..."$$."+:IccI"!~!!!$$!!!!+$R+$$"~!!!"~.".."""""".".""".""" """"""""+vcIo+"""""""""""$$$#.:co~co~!!!!!!!!!:vcI:~""+!~!~""""""."""""""""""""" """"""":cwIo+.""""""""""~$$"+co" !! !!!!!!!!!!!". +v!!"""""""""""""""""""""""""""" Icow "+co"~!!~!!!!!!!!!!!".~+v!!""""""""""""""""""""""" """""~Icow"+co" !! !!!!!!!!!!!". +v!!"""""""""""""""""""""""""""" Icow$~"""@~""""..#$$#~"":cII.~"~!!!!!!!!+".:.::~"""""""""""""~"""""""""~ """"~occooI$$B""#$#""~".P:""""~"~!Ico"""~!!!!+!~.. v+!"""B"""""""""""""""~"""""" """~~cccwc+BR~""R$$$"""""""""~"~:c"+co.""~"+~!. v:~""""".BB""~"~~"""~""""~""""" "~"!vcccwc".~"""R$$$$$X""""~~"~PcI".+vc."""~. .~!~~""~""~w!!R.""""~"""""""!""~"" """!!Icwo:""""+II$$$$!""""~0$o.""~:cI... !~"""~"":+:!!+!"!X""~"""~"""!v""""" """".."".~~"!IIIoo!#$$$"~"~wo$$"""""~~!~~"."~"""~$""~"$$~!~"""~~"~"~:c""~""~ "...""":+~"vIIIoIc~"PR@R@R@$~"."R#P~.~"""".. ".~~~v""@~~v~~~~~"c"~~~"~:c~~"~~~~ ~..~~:!!~~cIIo:   IIo:~~~IIo:   $@@@$$v~~.+XX~.""""""".!" ~~"~~v~c"~~~~~cI+~~~~!II+!~"~~~~ "".".":II+$R$#!~~~~$$$#@@@$$0P!~!XXv!"~"""":!!. ~~~v!P~~~~~~~vo++~~~!Ioc+~~~~~~~ ".~~.!~Ico$@B$$##B@@@@$#I00wXPPXv~~~"~o0!!~~.~~~~~~~~~~~!oo+:~~!Icc!+~"~~~~~ "~!!!~!I!":!$@@@@B@B@@@@@$0c0XPwXXXXXX~~+Xww+!!~~. "~~~~~~~~voI!!~~+occ!~~~~~~~+ +"!!..""~~::~@@@@@@@@@@@R$wIXPXXXPXXXPXPcw0w~!!!~... . .~~~~~..""""wwc++~"~~~:I~ ~+!.""~~~"~P@@@@@@@@@@@@R$$0$#$$XXXXXXX0X00+!+!!"... .....vv"!~~~~~IoI!~"."!oc!~ "".~""~!+XXP#@@~:+o@@@@@@@@B$$$XXXXX00Xc00I++!!!...... . cI~!!!~~!:Ic~~"".oc~"~ "~.""~~~coXP:"~~":P@@@@@BB$$#$PXXXPXX0c000+++!!!.... ... vcI"!!!!!"!vv""~~::"~++ !!"."~~~~+."~"~"~.PRBBR#w$wXXXXXXXP00oXXX+++!!!..... . II"+~!~!!.c+:""~.!!+ww: ~!+:+.."~."""""".X0PXXX+0oXXP0P0P00XoXo0++:+!~!.........Ic!!~!!~.!!v~".""~Iow++~ "+!~:."~.~.".~"~I0XXXX~:!P0XXwXoX0oXcXo+!!+!~!".. ... :I~!!~!~~~"!~~".~~oI!!+~" ~!+!"~~~."..""..".!+v~~~"X0XXwXcXww0I0ov++~!!... ....c:~!!!!~!~"~~.!!!~~:o!!~""~ "!!"~~~""~..."~~~.~!!.~""o0Iw".$P$$0""~II!!!... ..cv~"!!~!!~!"~~""""~!!~w:~~""". !."!!!"~~~~~~~~~~ "~"~"".v0""###$##$#wX"v:!!!+!!!!!~!!!+~+!~~"!.""..".v:I"""~~"" "~!!~+~~~~~~~~~"~".".".++c..""$##$#P$ww""+!!!!!!!!~!!!!"~!~.~"~."~."~!:~"".""".. */