该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

小杨构建了一个由 $n$ 个魔法石组成的线型阵列，魔法石依次编号为 $1,2,\dots,n$，第 $i$ 个魔法石的能量值为 $a_i$。注意，$a_i$ 可能为负数，表示这块魔法石会消耗能量。

现在小杨需要从中挑选出两段互不重叠的非空连续子数组，开启“双重魔法阵”，并使这两段子数组的能量值之和尽可能大。

请你编写程序，计算这个最大总能量。

输入格式

第一行一个正整数 $n$，表示魔法石的数量。

第二行 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示每个魔法石的能量值。

输出格式

输出一行，一个整数，表示两段互不重叠连续子数组的最大能量和。

5
1 -2 3 5 -1

9

4
-3 -1 -4 -2

-3

说明/提示

样例 1 解释：

一种最优方案是第一段选择 [1]，第二段选择 [3,5]，总能量为 $1 + (3+5) = 9$。

样例 2 解释：

所有数都是负数时，仍然必须选择两段非空连续子数组。为了让总和最大，应选择数值最大的两个单元素子数组 [-1] 和 [-2]，总和为 $-3$。

对于 $40\%$ 的测试点，保证 $2 \le n \le 10^3$。

对于所有测试点，保证 $2 \le n \le 10^5$，$-10^9 \le a_i \le 10^9$。