照相机

• 时间限制：$1$ 秒
• 空间限制：$512\text{ MB}$

题目描述

给定 $n$ 个整数 $a_1,a_2,\dots,a_n$。

你需要选出若干个区间 $[l,r]$，满足：

1. 被选区间互不包含；
2. 对于每个不大于 $n$ 的正整数 $i$，至少有一个被选区间覆盖位置 $i$。

请你求出所有被选区间的区间和之和的最大值。

定义：

• 区间 $[l,r]$ 包含区间 $[l',r']$，当且仅当 $l\le l'$ 且 $r\ge r'$。
• 区间 $[l,r]$ 覆盖位置 $i$，当且仅当 $l\le i\le r$。
• 区间 $[l,r]$ 的区间和等于 $\sum_{i=l}^r a_i$。

输入格式

输入第一行包含一个正整数 $n$，表示序列的长度。

输入第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$，表示给定的序列。

输出格式

输出一行一个整数，表示答案。

样例 1 输入

3
-1 3 2

样例 1 输出

7

样例 1 解释

最优解选取的区间为 $[1,2]$ 和 $[2,3]$，它们满足互不包含且覆盖了 $1$ 到 $n$ 的所有位置。故答案为 $-1 + 3 + 3+ 2 = 7$。

样例 2 输入

5
3 1 -4 -1 5

样例 2 输出

5

样例 3 输入

6
4 5 2 -3 1 -6

样例 3 输出

11

数据规模与约定

本题使用捆绑测试。 各个子任务对应的特殊数据范围如下：

• Subtask 1（10 分）：$n\le 5$；
• Subtask 2（20 分）：$n\le 300$；
• Subtask 3（20 分）：$n\le 5000$；
• Subtask 4（20 分）：$a_i \ge 0$；
• Subtask 5（30 分）：无特殊限制。

对于所有数据，满足 $1\le n\le 5\times 10^5$，$|a_i|\le 10^6$。