Description

超超是个吃货，有一天，她来到了神奇的魔法谷，这里有一条单行道路， 超超为了吃到世界上最美味的食物，必须要穿过这条道路。 这是一个长度为 N 的魔法道路，超超需要从 1 走到 N。每个单位长度上有一个蘑菇，因为超超是个大吃货，所以她总是控制不住自己，必须要吃掉在眼前的食物。但是这些蘑菇受到了魔法的影响，有的可以增加超超的生命，有的可以减少超超的生命。当超超的生命小于 $0$ 时，超超就不能前进， 被召回现实世界了，现在超超希望大家告诉她，她最少需要有多少初始生命值，才能通过这条魔法道路，吃到世界上最美味的食物？

Input

第 $1$ 行：一个数 N，表示魔法道路的长度。$（1 \leq N \leq 50000）$ 接下来的 $N$ 行，每行一个数 A[i]，表示第 i 个单位上有一个魔法蘑菇，可以对超超的生命增加 A[i]（如 果 A[i] > 0，表示超超生命增加 A[i]，如果 A[i] < 0，表示超超生命减少 A[i]）。 其中$-1000000000 <= A[i] <= 1000000000$。

Output

输出超超通过魔法道路的最小初始生命。

Sample Input

5
1
-2
-1
3
4

Sample Output

2