Maximum Beauty Value

You are given an integer n and an array of n integers representing the beauty values of plants. Your task is to find the maximum beauty value that can be achieved by selecting a contiguous subarray, with the possibility of adding one extra plant from outside the subarray. In other words, you may either choose a contiguous segment of the array or choose a contiguous segment and then add one additional element (which is not part of the chosen segment) to increase the total beauty value.

Formally, if the contiguous subarray has a sum S and there exists an element x not included in that subarray, then you can obtain a beauty value of S + x. Your answer is the maximum beauty value obtainable under these rules. Note that you are not forced to add an extra element if it does not improve the result.

The input guarantees that there is at least one plant. Consider the examples below:

• For a single plant with beauty 5, the maximum beauty is 5.
• For a single plant with beauty -5, the maximum beauty is -5.
• For an array [1, 2, 3, 4, 5], the optimal selection is the whole array giving 15.
• For an array [-1, 2, -3, 4, -2], selecting the subarray [4] and adding the extra element 2 yields a total of 6.
• For an array [-1, -2, 3, 4, 5, -6], the best contiguous sum [3,4,5] is 12 and adding any extra does not improve it.

inputFormat

The first line contains a single integer n (1 ≤ n ≤ 10⁵), representing the number of plants.

The second line contains n space-separated integers, each representing the beauty value of a plant. The beauty values may be negative, zero, or positive.

outputFormat

Output a single integer — the maximum beauty value achievable under the given rules.

1
5

5