405128: GYM101804 A Adaptation Stories

During the military adaptation period, the candidate DH forgot to bring his water bottle to drill. So that he would not run out of water, the military training leaders lent him a water gallon, affectionately called by minalbinha. However it should also be used to resupply the water bottle of the other candidates.

During the training, the military training leaders will bring some amount of water to refill minalbinha and the other candidates will take some amount of water from minalbinha to refill their bottles.

DH, being the responsible for minalbinha, knows the order and the amount of water of every request. He asked your help to determine the minimum amount of water needed to bring on minalbinha so that every request can be satisfied.

Consider that minalbinha can carry any amount of water.

The first line of input contains one integer, $$$n$$$ ($$$0 \leq n \leq 10^5$$$) — the number of requests.

The next line contains $$$n$$$ integers, $$$v_i$$$ ($$$-1000 \leq v_i \leq 1000$$$, $$$v_i \neq 0$$$) — the amount of water of $$$i$$$-th request. If $$$v_i$$$ is negative, the water is being taken from minalbinha, otherwise the water is being given to minalbinha.

Print the minimum amount of water that is needed to bring on minalbinha to fulfill all requests.

7
2 1 -1 -4 3 -5 3

4

3
10 3 -10

0

3
-10 -10 -10

30