406840: GYM102569 E Fluctuations of Mana

A mage is going to visit $$$n$$$ magical sources in fixed order. It is known that after visiting the $$$i$$$-th source the mana is changed by $$$a_i$$$ (this number can be positive, negative or zero). If the mage's mana becomes negative, he dies. What minimal amount of mana should the mage have in the beginning of his journey to successfully visit all $$$n$$$ sources and stay alive?

The first line contains an integer $$$n$$$ ($$$1 \le n \le 500000$$$) — the number of magical sources.

The second line contains $$$n$$$ integers $$$a_i$$$ ($$$-10^9 \le a_i \le 10^9$$$) — the mana change after visiting the $$$i$$$-th source.

Output one integer — the minimal amount of mana the mage should have to successfully complete his journey.

6
3 -4 2 -3 -2 7

4