题目描述

控制中心已经排好了一份包含 $n$ 条指令的计划。系统的储备值初始为 $0$，执行一条数值为 $a_i$ 的指令后，储备值增加 $a_i$。$a_i$ 可以为正数、负数或零。

在开始执行前，你至多可以选择一个非空连续区间 $[l,r]$，将这个区间内指令的执行顺序翻转。也就是说，

会变为

指令的数值不会改变，也不会变号；区间外指令的顺序不变。选择长度为 $1$ 的区间不会改变计划，因此也表示不进行有效调整。

调整后，记执行完前 $i$ 条指令时的储备值为 $H_i$。一份计划的安全值定义为

初始值 $H_0=0$ 不计入上述最小值。

请输出所有合法选择中，安全值的最大可能值。

输入格式

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

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

本题只有一组测试数据，并保证：

• $1\le n\le 5000$；
• $-10^9\le a_i\le 10^9$。

所有执行过程中的储备值以及答案都能用有符号 $64$ 位整数表示。

输出格式

输出到文件 reverseplan.out 中。

输出一个整数，表示最大的安全值。

答案由输入唯一确定。采用标准判题，按空白分隔比较这个整数。

样例输入 #1

5
-5 4 -2 6 -1

样例输出 #1

2

样例解释

选择区间 $[1,4]$ 后，指令序列变为

各次执行后的储备值依次为 $6,4,8,3,2$，安全值为 $2$。无论怎样翻转，最后的储备值 $H_5$ 都等于所有指令之和 $2$，所以安全值不可能超过 $2$。因此答案为 $2$。

数据规模与约定

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。除下表列出的额外条件外，每个子任务均满足完整输入限制。

下发文件

包含本题额外3组大数据的输入与输出文件。

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