Maximum Sum Subarray Segment

You are given an array of integers. Your task is to find a contiguous subarray (segment) that has the maximum possible sum and output its start and end indices (1-based). In case there are multiple segments with the same maximum sum, choose the segment with the smallest length.

Mathematically, if the subarray from index (i) to (j) (1-based) has a sum (S = \sum_{k=i}^{j} a_k), then you need to maximize (S) and, in case of ties, minimize (j-i+1).

inputFormat

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

outputFormat

Output two integers separated by a space – the 1-based starting and ending indices of the contiguous segment with the maximum sum.## sample

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

4 7