Sum of Maximum and Minimum Subarray Sums

You are given an array of n integers. Your task is to compute two values:

• The maximum subarray sum (i.e. the maximum value of \(\sum_{k=i}^{j} a_k\) for any 0 \(\leq\) i \(\leq\) j \(\lt\) n), which can be found using Kadane's algorithm.
• The minimum subarray sum (i.e. the minimum value of \(\sum_{k=i}^{j} a_k\) for any 0 \(\leq\) i \(\leq\) j \(\lt\) n).

You should then output the sum of these two values.

Example: For the array [1, -2, 3, -2, 5], the maximum subarray sum is 6 and the minimum subarray sum is -2, so the output is 4.

inputFormat

The first line of input contains a single integer n (1 \(\leq n \leq 10^5\)), the number of elements in the array.

The second line contains n space-separated integers denoting the elements of the array.

outputFormat

Output a single integer representing the sum of the maximum subarray sum and the minimum subarray sum.

## sample

5
1 -2 3 -2 5

4

</p>