Maximum Subarray Sum with Indices

You are given an array of integers. Your task is to find the contiguous subarray within the array which has the largest sum. In addition to the maximum sum, you must also output the starting and ending indices (0-indexed) of this subarray.

Recall Kadane's algorithm, which finds the maximum subarray sum in \(O(n)\) time. Formally, given an array \(A = [a_0, a_1, \dots, a_{n-1}]\), find indices \(i\) and \(j\) such that the sum \(S = \sum_{k=i}^{j} a_k\) is maximized. In the event of multiple subarrays having the same maximum sum, choose the one that appears first.

Note: If the array contains only negative numbers, choose the subarray with the single maximum element (i.e. the least negative number), and consider its start and end indices as the same index.

inputFormat

The first line of input contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers.

outputFormat

Output three space-separated integers: the maximum subarray sum, the starting index, and the ending index of the subarray that produces this maximum sum.

## sample

5
1 2 3 -2 5

9 0 4

</p>