Maximal Subarray Sum with Minimal Range

You are given an array of integers. Your task is to find a non-empty contiguous subarray that yields the maximum possible sum. In case multiple subarrays have the same maximum sum, choose the one with the smallest range (i.e. the difference between the maximum and minimum elements in the subarray is minimized).

Note: The subarray must be contiguous.

inputFormat

The first line of input contains a single integer n (n ≥ 1), representing the number of elements in the array. The second line contains n space-separated integers.

outputFormat

Output a single integer, which is the sum of the subarray that satisfies the conditions.

5
3 -1 2 7 -4

11