题目描述

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

请问这个最大和是多少？

输入

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

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

输出

输出最大和。

样例

7
2 -4 3 -1 2 -4 3

7

说明

【样例解释】

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

【数据范围】

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

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

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