Maximum Segment Score with One Deletion

You are given an array of n integers. Your task is to select a contiguous segment (a non‐empty subarray) and compute its score, which is defined as the sum of its elements. In addition, you are allowed to remove at most one element from the entire array to possibly obtain a higher score. However, if an element is removed, the remaining segment must be exactly one of the contiguous subarrays of the original array with that element removed.

In other words, the answer is the maximum among the following two quantities:

1. The maximum sum of any contiguous subarray (the standard Kadane’s algorithm result).
2. For arrays with more than one element, the maximum value of the total sum of the entire array after removing one element (i.e. total_sum - x for some element x), which is equivalent to choosing the contiguous segment that is the entire array with a removal from one of its boundaries.

Note that when n = 1, no deletion is allowed as the segment must be non‐empty.

It is guaranteed that this interpretation yields the expected outputs in the sample cases.

Mathematical Formulation:

Let \(A = [a_0, a_1, \dots, a_{n-1}]\) be the array. Define

[ Kadane = \max_{0 \leq i \leq j < n} \sum_{k=i}^j a_k, ]

and if \(n > 1\), define

[ Removal = \max_{0 \leq i < n} \Bigl(\sum_{k=0}^{n-1} a_k - a_i\Bigr). ]

The answer is

[ answer = \begin{cases} a_0, & n = 1,
\max(Kadane, Removal), & n > 1. \end{cases} ]

</p>

inputFormat

The input is read from standard input (stdin) and has the following format:

n
a1 a2 ... an

Where n (1 ≤ n ≤ 10⁵) is the number of elements, and each ai is an integer (which can be negative) separated by spaces.

outputFormat

Output a single integer — the maximum segment score according to the problem description. The output should be written to standard output (stdout).

## sample

5
1 -2 3 4 -5

7