题目描述

有编号 $1-n$ 的 $n$ 个格子，机器人从 $1$ 号格子顺序向后走，一直走到 $n$ 号格子，并需要从 $n$ 号格子走出去。机器人有一个初始能量，每个格子对应一个整数 $A[i]$ ，表示这个格子的能量值。如果 $A[i] > 0$ ，机器人走到这个格子能够获取 $A[i]$ 个能量，如果 $A[i] < 0$ ，走到这个格子需要消耗相应的能量，如果机器人的能量 < $0$ ，就无法继续前进了。问机器人最少需要有多少初始能量，才能完成整个旅程。

例如： $n = 5$ 。{ $1$ ， $-2$ ， $-1$ ， $3$ ， $4\}$ 最少需要 $2$ 个初始能量，才能从 $1$ 号走到 $5$ 号格子。途中的能量变化如下 $3\ 1\ 0\ 3\ 7$ 。

输入格式

第 $1$ 行： $1$ 个数 $n$ ，表示格子的数量。 $(1 \le n \le 50000)$ 第 $2 - n + 1$ 行：每行 $1$ 个数 $A[i]$ ，表示格子里的能量值( $-10^9 \le A[i] \le 10^9)$

输入格式

输出 $1$ 个数，对应从 $1$ 走到 $n$ 最少需要多少初始能量。

5
1
-2
-1
3
4

2