Maximum Profit from Two Non-Overlapping Subarrays

You are given an array of integers. Your task is to choose exactly two non-overlapping contiguous subarrays (each containing at least one element) such that the total profit (i.e. the sum of the elements in both subarrays) is maximized.

Formally, let the given array be \(A[0 \dots n-1]\). You need to select two indices \(i, j\) (with \(0 \leq i < j < n\)) such that one subarray is from some \(s_1\) to \(e_1\) (with \(0 \leq s_1 \leq e_1 < j\)) and the other is from \(s_2\) to \(e_2\) (with \(j \leq s_2 \leq e_2 \leq n-1\)). The goal is to maximize:

[ \text{Profit} = \left(\sum_{k=s_1}^{e_1} A[k]\right) + \left(\sum_{k=s_2}^{e_2} A[k]\right). ]

If the array contains only negative numbers or a mix of positive and negative numbers, the optimal subarrays might consist of a single element. For example, for the input [-1, -2, -3, -4, -5, -6], the answer is -3 since selecting \(-1\) and \(-2\) yields the maximum possible sum of \(-3\).

Input Format: The first line contains an integer \(n\) (\(n \geq 2\)), the number of elements in the array. The second line contains \(n\) space-separated integers.

Output: Output a single integer representing the maximum possible profit.

Note: The two subarrays must be non-overlapping and each must contain at least one element.

inputFormat

The input is read from stdin and consists of two lines:

1. The first line contains an integer \(n\), representing the number of elements in the array \(A\).
2. The second line contains \(n\) space-separated integers, which are the elements \(A[0], A[1], \dots, A[n-1]\) of the array.

outputFormat

Print a single integer to stdout — the maximum profit achievable by selecting two non-overlapping subarrays from the given array.

## sample

6
3 2 5 1 6 4

21