Maximum Subarray Sum and Subarray Length

You are given an array of integers. Your task is to find the contiguous subarray (containing at least one number) that has the largest sum. In addition, you must also determine the length of that subarray. In case there are multiple subarrays with the same maximum sum, the subarray with the smallest length is chosen. If there is still a tie, choose the one that starts at the smallest index.

Note: If the array consists entirely of negative numbers, then the maximum subarray is the single element with the highest value.

The answer should be printed as two numbers separated by a space: the maximum sum followed by the length of the subarray.

inputFormat

The first line of input contains a single integer T, the number of test cases. Each test case consists of two lines:

1. The first line contains an integer N, the size of the array.
2. The second line contains N space-separated integers representing the elements of the array.

All input is given via stdin.

outputFormat

For each test case, output a single line containing two space-separated integers: the maximum contiguous subarray sum and the length of the corresponding subarray. The output should be printed to stdout.

## sample

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

7 2
6 3
-1 1
6 4

</p>