Maximum Subarray Sum with Indices

You are given an array of integers of length \( n \). Your task is to find the contiguous subarray (containing at least one number) which has the largest sum. Print the maximum sum along with the starting and ending indices (both inclusive) of that subarray.

If there are multiple subarrays with the same maximum sum, choose the one with the smallest starting index. If there is still a tie, choose the one with the smallest ending index.

The problem can be formalized as finding indices \( i \) and \( j \) (with \( 0 \le i \le j < n \)) such that the sum \( S = \sum_{k=i}^{j} a_k \) is maximized. In case of ties, pick the subarray with the least \( i \), and if still tied, the least \( j \).

inputFormat

The first line of the input contains an integer \( n \) denoting the number of elements in the array.

The second line contains \( n \) space-separated integers representing the elements of the array.

outputFormat

Print three space-separated integers: the maximum contiguous subarray sum, the starting index, and the ending index of the subarray.

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

6 3 6