SDE Path

Print the Subarray with Maximum Sum

Medium

Print the Subarray with Maximum Sum

Extend Kadane's algorithm to also return the start and end indices of the maximum sum subarray.

Input format

The first line contains N. The second line contains N space-separated integers.

Output format

Print two 0-based indices l r — the bounds of the maximum-sum subarray. If several subarrays tie, print the one with the smallest l, then the smallest r.

Constraints

  • Values fit in a 64-bit signed integer
  • Trailing whitespace and a trailing newline are ignored by the judge

Read from stdin, write to stdout. Sample cases below show the exact format.

Sample cases

Example 1
Input
9
-2 1 -3 4 -1 2 1 -5 4
Expected output
3 6
Example 2
Input
1
-1
Expected output
0 0