Maximum Subarray Sum and Indices

You are given an array of n integers. Your task is to find a contiguous subarray whose sum is maximum and output the maximum sum along with the starting and ending indices (0-indexed) of that subarray.

If there are multiple contiguous subarrays yielding the same maximum sum, choose the one with the shortest length. If there is still a tie, choose the one that starts at the smallest index.

You can express the sum of a subarray from index i to j as:

\( S = \sum_{k=i}^{j} a[k] \)

inputFormat

The input is given from standard input (stdin) and has two lines:

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

outputFormat

Print three space-separated integers to standard output (stdout): the maximum sum, the starting index, and the ending index of the subarray.

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

6 3 6