Maximum Sum Subarray with One Removal

Given an array of integers, the task is to find the maximum sum of any contiguous subarray, with the twist that you are allowed to remove at most one element from that subarray.

You are given an integer \(n\) denoting the size of the array and \(n\) integers \(a_1, a_2, \ldots, a_n\). You may choose any contiguous segment of the array and optionally remove one element from it to maximize the sum of the remaining numbers. Note that if removing an element does not improve the sum, you may choose to not remove any element.

In other words, you need to compute:

$$ \max_{1 \leq i \leq j \leq n} \left\{ \; \max \left( \sum_{k = i}^{j} a_k, \; \sum_{k = i}^{j} a_k - a_t \right) \; \text{for some } t \text{ with } i \leq t \leq j \right\} $$

If the array consists of a single element, simply output that element.

inputFormat

The input is given via standard input and consists of two lines:

• The first line contains an integer \(n\), the number of elements in the array.
• The second line contains \(n\) space-separated integers representing the array elements.

outputFormat

Output a single integer — the maximum sum obtainable from any subarray after at most one removal, printed to standard output.

## sample

5
1 -2 0 3 -1

4

</p>