Maximum Subarray with Indices

You are given an array of integers. Your task is to find the contiguous subarray with the maximum sum and output the sum along with its starting and ending indices. This is a classic problem that is commonly solved using Kadane's algorithm. In mathematical terms, given an array \(a_0, a_1, \dots, a_{n-1}\), you need to find indices \(i\) and \(j\) (with \(0 \leq i \leq j < n\)) such that the sum \(S = \sum_{k=i}^{j} a_k\) is maximized.

Note: If multiple subarrays yield the same maximum sum, output the one which appears first in the array, i.e. with the smallest starting index.

inputFormat

The first line of input contains a single 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 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