Kompanija

Kompanija ima listu očekivanih prihoda i rashoda za predstojeću godinu, u hronološkom redosledu. Problem nastaje jer u nekom trenutku, suma prethodnih prihoda može biti manja od sume rashoda, što bi kompaniju uvelo u dug. Da bi izbegla ovo, kompanija koristi vrlo jednostavno rešenje, prebaci neki rashod za kraj godine.

Opis ulaza

Dat je ceo broj \(n\) (\(1 \leq n \leq 100000\)), i potom \(n\) celih brojeva, gde pozitivni brojevi predstavljaju prihode, a negativni rashode, u hronološkom redosledu. Svaki od brojeva pripada intervalu \([-1000, 1000]\). U jednom potezu možemo da realociramo jedan rashod za kraj godine.

Opis izlaza

Na standardni izlaz ispisati koliko najmanje realokacija rashoda je potrebno, tako da kompanija ne uđe u dug. Može se pretpostaviti da je suma ulaznog niza nenegativna.

Primer 1

Ulaz

5
10 -10 -1 -1 10

Izlaz

1

Primer 2

Ulaz

7
-1 -1 -1 1 1 1 1

Izlaz

3

Primer 3

Ulaz

4
5 -2 -3 1

Izlaz

0