Maximum Subarray Sum with Indices

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

In mathematical terms, for an array \(a[0 \ldots n-1]\), you need to find indices \(i\) and \(j\) such that the sum \(S = \sum_{k=i}^{j} a[k]\) is maximized. The result should be printed as three numbers:

Maximum Sum, Starting Index, and Ending Index.

Note: If all elements are negative, the answer is the maximum element and its index (both start and end indices will be the index of that element).

inputFormat

The first line contains a single integer \(n\) (\(1 \leq n \leq 10^5\)) representing the number of elements in the array.

The second line contains \(n\) space-separated integers \(a[0], a[1], \ldots, a[n-1]\) which can be positive, negative, or zero.

outputFormat

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

## sample

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

6 3 6

</p>