Maximum Sum of Two Separated Subarrays

Given an integer sequence of length \( n \), you are required to select two contiguous subarrays (each of at least length \(1\)) such that there is at least one element between them, and the sum of the numbers in these two subarrays is maximized. A contiguous subarray is defined as a sequence of consecutive elements, and its sum is the sum of all numbers in it. Your task is to output this maximum possible sum.

Note: The two subarrays must be separated by at least one element (i.e. if the first subarray ends at index \( j \), then the second subarray must start at an index \( k \) where \( k \geq j+2 \)).

Example:

For the sequence [1, 2, -1, 3, 4], one possible optimal selection is the subarrays [1, 2] and [3, 4] with a gap (the element -1). Their sums are 3 and 7 respectively, giving a total of 10.

inputFormat

The first line contains a positive integer \( n \) (\( n \ge 3 \)), the length of the sequence.

The second line contains \( n \) space-separated integers representing the sequence.

outputFormat

Output a single integer representing the maximum sum obtainable by selecting two separated contiguous subarrays.

sample

5
1 2 -1 3 4

10