Description

Given an integer sequence of length $n$, select two subarrays (contiguous, non-empty segments of the sequence) such that the total sum of the integers in these two subarrays is maximized, and output that total sum. Each subarray must have a minimum length of $1$, and the two subarrays must be separated by at least one element.

Input Format

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

Output Format

Output a single integer, the maximum total sum of the integers in the two selected subarrays.

5
83 223 -13 1331 -935

1637

3
83 223 -13

70

Hint

Constraints:

• For $30\%$ of the testdata, $n \le 100$.
• For $60\%$ of the testdata, $n \le 10^4$.
• For $100\%$ of the testdata, $n \le 10^6$.
• All values during the computation are guaranteed to fit within the range of a signed $64$-bit integer.

Translated by ChatGPT 5