Maximum Subarray Sum with Indices

Given an array of integers, you are to find a contiguous subarray (containing at least one element) that has the maximum possible sum. You need to output the maximum sum along with the starting and ending indices (1-indexed) of this subarray.

If there exist multiple subarrays with the same maximum sum, choose the one with the smallest starting index; if there still exists a tie, choose the one with the smallest ending index.

This problem can be mathematically formulated as follows:

\( \text{MaxSum} = \max_{1 \leq i \leq j \leq n} \sum_{k=i}^{j} a_k \)

inputFormat

The first line contains an integer n denoting the number of elements in the array.

The second line contains n space-separated integers representing the array elements.

outputFormat

Output three space-separated integers: the maximum subarray sum, the starting index, and the ending index of the subarray. Indices are 1-indexed.

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

6 4 7