Maximum Height Sum Subarray

You are given an array of integers. Your task is to find a contiguous subarray (i.e. a subsegment) whose height sum is maximum. Formally, given an array \(a_1, a_2, \dots, a_n\), find indices \(L\) and \(R\) (with \(1 \le L \le R \le n\)) such that the sum \(S = \sum_{i=L}^{R} a_i\) is maximized.

In case there are multiple subarrays with the same maximum sum, choose the one with the smallest length (i.e. minimize \(R-L+1\)). If there is still a tie, choose the leftmost subarray. Finally, output the 1-indexed positions for the starting and ending indices of this subarray.

Note: The array may contain negative numbers. In such cases, the subarray with the maximum sum might be a single element.

inputFormat

The input is given via standard input (stdin) and has the following format:

n
 a1 a2 ... an

Where:

• \(n\) is an integer representing the number of elements in the array, with \(1 \le n \le 10^5\).
• \(a1, a2, \dots, an\) are the space-separated integers of the array (each can be negative or positive).

outputFormat

Print via standard output (stdout) two integers separated by a space: the starting index \(L\) and the ending index \(R\) (both 1-indexed) of the subarray with the maximum sum, adhering to the tie-breaking rules described above.

9
-2 1 -3 4 -1 2 1 -5 4

4 7