Maximum Subarray Sum with Indices

Given an array of integers, the task is to find a contiguous subarray that has the maximum sum and return the sum along with the 1-indexed start and end positions of that subarray. In case of multiple answers, return the one with the earliest starting index.

This problem can be solved using an adaptation of Kadane's Algorithm. The main idea is to iterate through the array while keeping track of the current subarray sum and updating the best (maximum) sum found so far. The recurrence relation can be written in LaTeX as follows: $$current\_sum = \max(arr[i], current\_sum + arr[i])$$ and the overall maximum as $$max\_sum = \max(max\_sum, current\_sum)$$.

You need to process multiple test cases. For each test case, the input is provided via standard input and your solution should output the result to standard output.

inputFormat

The first line of input contains an integer T, representing the number of test cases. Each test case begins with a line containing an integer N (the size of the array), followed by a line with N space-separated integers representing the elements of the array.

outputFormat

For each test case, output a single line containing three space-separated integers: the maximum subarray sum, the start index, and the end index of the subarray (all 1-indexed).

## sample

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

6 4 7
15 1 5

</p>