// I am soo weak :( #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; struct SegmentTree { vi st, a; int n; const int empty = INF; int merge(int a, int b) { return min(a, b); } void init(int _n, vector<int> A) { n = _n; st.resize((n<<2)|1); a.resize(n + 1); for (int i = 1; i <= n; i++) a[i] = A[i]; } void build(int l, int r, int v) { if (l == r) { st[v] = a[l]; return; } int mid = (l + r)>>1; build(l, mid, v<<1); build(mid + 1, r, v<<1|1); st[v] = merge(st[v<<1], st[v<<1|1]); } int getans(int l, int r, int v, int val) { if (l == r) return l; int mid = (l + r)>>1; if (st[v<<1|1] <= val) return getans(mid + 1, r, v<<1|1, val); else if (st[v<<1] <= val) return getans(l, mid, v<<1, val); return 0; } int getans(int l, int r, int val) { return getans(l, r, 1, val); } void update(int l, int r, int pos, int val, int v) { if (l > pos || pos > r) return; if (l == r) { st[v] = val; return; } int mid = (l + r)>>1; update(l, mid, pos, val, v<<1); update(mid + 1, r, pos, val, v<<1|1); st[v] = merge(st[v<<1], st[v<<1|1]); } void update(int pos, int val) { update(1, n, pos, val, 1); } }; 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]}; SegmentTree st; st.init(n, vector<int> (n + 1, inf)); st.build(1, n, 1); st.update(1, p[1] + dp[1][1]); for (int i = 2; i <= n; i++) { int ind = st.getans(1, n, p[i]); assert(dp[ind][1] <= p[i] - p[ind]); dp[i] = {dp[ind][0] + 1, p[i] - p[ind]}; st.update(i, dp[i][1] + p[i]); } 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""+!!!!!!!!~!!!!"~!~.~"~."~."~!:~"".""".. */