题目描述

给定 $n$ 个整数，请从 $n$ 个整数中选择互不相交的 $2$ 个连续的区间，使得这两个区间的所有数的和尽可能大。

请问这个最大和是多少？

输入格式

第一行一个正整数 $n$ ，表示整数数量。

接下来一行有 $n$ 个整数 $a_i$。

输出格式

输出最大和。

样例输入 #1

7
2 -4 3 -1 2 -4 3

样例输出 #1

7

数据范围

【样例解释】

选 $[3,5]$ 和 $[7,7]$ 两段的和是最大的。

【数据范围】

对于 $30\%$ 的数据，$n≤100$；

对于另外 $30\%$ 的数据，$n≤1000$；

对于 $100\%$ 的数据，$n≤10^5$，$−10^9≤a_i≤10^9$。