Disjoint Subarrays Max Sum

You must cut the array at some adjacent position into a non-empty left part and a non-empty right part, both contiguous. Find the maximum non-empty contiguous subarray sum of the left part and of the right part separately, then add the two; return the maximum over all cuts. The cut point and the maximum subarrays within the two parts may vary independently.

输入格式

The first line contains n; the second line contains n integers a[i]. This site adds 2≤n≤200000 and −1000000000≤a[i]≤1000000000, so that both parts are non-empty and the sums are safe in 64 bits.

输出格式

Output one integer, the best sum over all valid cuts.

样例 1

输入：

6
-1 4 -2 5 -3 6

输出：

13

样例 2

输入：

2
-5 -2

输出：

-7

样例 3

输入：

3
2 -10 3

输出：

5