E. Fluctuations of Mana
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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?

Input

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

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

Example
Input
6
3 -4 2 -3 -2 7
Output
4