Problem Description

Given an integer sequence of length $n$, you are required to select two continuous subsequences such that the sum of these two continuous subsequences is maximized. You only need to output the maximum sum. The sum of a continuous subsequence is the sum of all numbers in that subsequence. Each continuous subsequence has a minimum length of $1$, and there must be at least one number between the two continuous subsequences.

Input Format

The first line contains an integer $n$.

The second line contains $n$ integers representing the integer sequence.

Output Format

A single number, the sum of the two continuous subsequences.

Sample Input and Output

Sample Input #1

5
83 223 -13 1331 -935

Sample Output #1

1637

Sample Input #2

3
83 223 -13

Sample Output #2

70

Notes

For $30\%$ of the data, $N \le 100$.

For $60\%$ of the data, $N \le 10000$.

For $100\%$ of the data, $N \le 1000000$.

The data guarantees that the computational process will not exceed long long (int64).

见题面 Input 部分

见题面 Output 部分