Maximum Performance Segment

You are given T test cases. For each test case, you must find a contiguous subarray (segment) of scores that has the maximum sum. In addition to the maximum sum, you must also determine the starting and ending indices (using 1-based indexing) of that segment.

In each test case, the first integer is N which represents the number of scores that follow. The next N integers represent the scores in sequence. Formally, if the scores are represented by \( a_1, a_2, \dots, a_N \), you need to find indices \( i \) and \( j \) such that the sum \( S = a_i + a_{i+1} + \dots + a_j \) is maximized.

If there are multiple segments with the same maximum sum, choose the segment with the shorter length. If there is still a tie, choose the one that starts earlier.

Note: The algorithm to solve this problem is a modified version of Kadane's algorithm.

inputFormat

The input begins with an integer T (\( 1 \leq T \leq 10 \)), the number of test cases. For each test case:

• The first line contains an integer N (the number of scores).
• The second line contains N space-separated integers representing the scores.

\( 1 \leq N \leq 10^5 \) and each score is an integer that can be negative or positive.

outputFormat

For each test case, output a single line containing three space-separated integers:

• The maximum sum of the contiguous subarray.
• The 1-based starting index of this subarray.
• The 1-based ending index of this subarray.

## sample

2
5
-1 2 3 -4 2
4
1 2 3 -6

5 2 3
6 1 3

</p>