题目描述

有 $n$ 个能量模块从左到右排成一行，第 $i$ 个模块的能量变化量为整数 $a_i$。

你需要选择一个非负整数 $E$ 作为初始能量。之后重复以下操作，直到所有模块都被激活：

• 选择当前剩余模块中最左边或最右边的一个并激活；
• 将该模块的能量变化量加到当前能量上，然后检查当前能量是否非负；
• 被激活的模块从这一行中消失。

如果每次激活后的能量都不小于 $0$，包括激活最后一个模块之后，那么这次激活顺序是安全的。

请计算最小的初始能量 $E$，使得至少存在一种安全的激活顺序。

输入格式

从文件 energy.in 中读取数据。

第一行包含一个整数 $n$，表示模块数量。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示各模块的能量变化量。

输出格式

输出到文件 energy.out 中。

输出一个非负整数，表示最小的初始能量 $E$。

3
3 -5 2

0

3
-4 10 -3

3

样例解释

样例 #1 中，取 $E=0$，依次激活原下标为 $1,3,2$ 的模块。每次激活后的能量依次为 $3,5,0$，因此这一顺序是安全的。由于初始能量不能为负数，答案不可能小于 $0$。

样例 #2 中，取 $E=3$，依次激活原下标为 $3,2,1$ 的模块。每次激活后的能量依次为 $0,10,6$。若取 $E=2$，第一次只能激活能量变化量为 $-4$ 或 $-3$ 的模块，激活后的能量都会小于 $0$，因此答案为 $3$。注意所有模块的能量变化量之和为正数，但初始能量仍不能取 $0$。

数据规模与约定

对于所有数据，保证：

• $1\le n\le 3000$；
• $-10^9\le a_i\le 10^9\ (1\le i\le n)$；
• $a_i$ 可以为正数、零或负数。

由于能量值和答案可能超过 $32$ 位有符号整数的范围，建议使用 $64$ 位整数。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数；各子任务独立计分。

下发文件

下载三组测试数据，非真实测试数据