Maximum Subarray Sum

Given an array of integers, your task is to find the contiguous subarray which has the largest sum, and output its sum along with the starting and ending indices (0-indexed) of the subarray.

If there are multiple subarrays with the same maximum sum, choose the one with the smallest starting index. If there is still a tie, choose the subarray with the smallest ending index.

This problem can be efficiently solved using a variant of Kadane's algorithm.

inputFormat

The first line of input contains a single integer n indicating the number of elements in the array. The second line contains n space separated integers representing the array elements.

outputFormat

Output three integers separated by a space: the maximum subarray sum, the starting index, and the ending index of the subarray with the maximum sum.

## sample

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

6 3 6

</p>