题目描述

一位探险家在沙漠中连续探险了 $n$ 天，每天都会记录物资变化：正数表示当天获得了补给，负数表示当天消耗了物资。

虽然记录了每天的物资变化，但出发时携带的初始物资量已经记不清了。

请你根据这份日志，计算出这位探险家出发时至少携带多少物资才能确保在探险期间物资储备始终不为负（不会出现"断粮"的情况）。

输入格式

• 第一行：单个整数表示 $n$。
• 第二行：$n$ 个整数 $a_1, a_2, dots, a_n$ 表示探险家每一天的物资储备的情况。

输出格式

输出一个整数，表示在出发之前，最少储备的物资数量。

样例

4
3 -2 -5 -1

5

5
-1 -2 1 -3 4

5

12
-1 -2 -3 4 -5 6 -3 -5 8 9 2 -4

9

提示

样例 1 解释：如果初始携带 $5$ 单位物资，那么每天的物资变化如下：

• 第 $1$ 天后：$5 + 3 = 8$
• 第 $2$ 天后：$8 - 2 = 6$
• 第 $3$ 天后：$6 - 5 = 1$
• 第 $4$ 天后：$1 - 1 = 0$

全程物资储备均不为负，满足要求。

数据范围

• 对于 $50\%$ 的数据，满足 $1 \le n \le 100$。
• 对于 $100\%$ 的数据，满足 $1 \le n \le 100000$，$-20000 \le a_i \le 20000$。