Maximum Subarray Sum with Indices

You are given an array containing n non-negative integers. Your task is to find the contiguous subarray that produces the maximum sum. In addition to finding the maximum sum, you must also output the starting and ending indices of this subarray.

Note: If the array is empty (n = 0), output "0 -1 -1". In case there are multiple subarrays with the same maximum sum, return the one that appears first.

The following recurrence describes the logic in Kadane's algorithm:

$$current\_sum = max(array[i], current\_sum + array[i]) $$

and update the maximum whenever current_sum exceeds the previous max_sum.

Indices are 0-based.

inputFormat

The input is given from standard input (stdin) and consists of two lines. The first line contains an integer n representing the number of elements in the array. The second line contains n space-separated non-negative integers representing the elements of the array.

outputFormat

Print three integers separated by spaces: the maximum subarray sum, the starting index, and the ending index. For an empty array (n=0), output "0 -1 -1".## sample

6
1 2 3 4 5 6

21 0 5