Cei N piraţi de pe Perla Neagră au făcut recent o captură foarte importantă: un cufăr cu 10 000 000 000 (zece miliarde) de bănuţi. Acum piraţii au de rezolvat o problemă şi mai dificilă: cum să împartă banii.
Pentru împărţire, piraţii se aşează în linie. Primul pirat va propune o schemă de împărţire a banilor. Dacă un anumit număr de piraţi nu sunt de acord cu această schemă, piratul va fi aruncat peste bord, şi apoi următorul pirat va propune o schemă de împărţire, şi tot aşa. Piraţii sunt foarte inteligenţi: un pirat este de acord cu o schemă de împărţire doar dacă aceasta îi aduce un avantaj strict (cel puţin un bănuţ) faţă de ce ar obţine votând împotriva schemei. Pentru că acţionează numai pe baze raţionale, piraţii sunt şi foarte predictibili. Cu alte cuvinte, un pirat poate anticipa decizia altor piraţi pentru a lua o decizie proprie (aceasta înseamnă şi că dacă un pirat are mai multe posibilităţi de a alege o schemă de împărţire, ceilalţi piraţi ştiu ce variantă ar alege).
Depinzând de caracteristicile fiecărui pirat (forţă, popularitate), numărul de piraţi care trebuie să fie de acord cu schema lui pentru a nu fi aruncat peste bord variază. Să zicem că pentru piratul i (1<=i<N) acest număr este A[i]. Dacă piratul i propune o schemă, ştim că toţi piratii până la i-1 au fost aruncaţi deja peste bord. În afară de piratul i, mai există N-i piraţi. Dacă cel puţin A[i] dintre aceştia sunt de acord cu schema piratului i, comoara va fi împărţită după această schemă. Altfel, piratul i va fi aruncat peste bord, şi piratul i+1 va propune o schemă. Pentru orice i, avem 0<=A[i]<N-i. Datorită acestei condiţii A[N-1]=0, iar A[N] nu este definit (pentru că piratul N este ultimul).
Cerinţă
Primul pirat din linie doreşte să propună o schemă de împărţire a banilor astfel încât să nu fie aruncat peste bord, şi el să primească cât mai mulţi bănuţi. Determinaţi suma maximă pe care o poate primi. Se garantează că există o schemă pe care o poate propune primul pirat, astfel încât el să nu fie aruncat peste bord.
Date de intrare
Fişierul de intrare caraibe.in conţine pe prima linie numărul N de piraţi. Pe următoarele linii se găsesc valorile A[1], A[2], ..., A[N-2], câte o valoare pe o linie. Aşa cum se menţionează mai sus, A[N-1] este întotdeauna zero şi nu apare în fişier.
Date de ieşire
Fişierul de ieşire caraibe.out va conţine o singură linie pe care va fi scris numărul maxim de bănuţi pe care îi poate primi primul pirat.
Restricţii
• 2 <= N <= 65 000
• 0 <= A[i] < N-i
Exemple
caraibe.in
caraibe.out
Explicaţii
4
1
1
9999999999
Schema propusă de primul pirat este: 9999999999 de bănuţi pentru el însuşi, 1 bănuţ pentru al treilea pirat şi 0 (zero) pentru ceilalţi. Asta îl face pe piratul al treilea să fie de acord cu schema. El raţionează astfel: „piraţii 2 şi 4 nu sunt de acord; dacă şi eu sunt împotrivă, piratul 1 va fi aruncat peste bord (A[1]=1); apoi piratul 2 va propune schema: 9999999999 de bănuţi pentru el însuşi, 1 bănuţ pentru piratul 4 şi nimic pentru mine; piratul 4 va fi de acord, deci schema va fi acceptată (A[2]=1); motivul pentru care piratul 4 va fi de acord este că în cazul în care piratul 2 e aruncat peste bord, eu îmi voi acorda toţi banii mie şi el nu primeşte nimic (A[3]=0)”.