## MAXSUMSQ - Maximum Sum Sequences

Given an array A having n elements, let X be the maximum sum of any contiguous sequence in the array. How many contiguous sequences in A sum up to X?

### Input

The first line contains T the number of test cases. There follow 2T lines, 2 for each test case. The first line contains the n, the number of elements in the array. The second line contains n space separated integers Ai.

### Output

Output T lines, one for each test case. On each line, output two space separated integers; the maximum sequence sum, and the number of sequences which obtain this maximum sum.

### Example

```Input:
23-1 -1 -142 0 -2 2

Output:
-1 32 4```

### Constraints

1 <= T <= 35
1 <= n <= 100000
-1000 <= Ai <= 1000

hide comments
 < Previous 1 2 3 Next > Ankit Sultana: 2015-03-20 11:26:09 Use long long for the number of sequences which obtain the maximum sum. Stupid Dog: 2015-02-28 05:04:20 scanf("%d\n", &n) : WA scanf("%d", &n) : AC

 Added by: Varun Jalan Date: 2010-01-24 Time limit: 1s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: NODEJS OBJC PERL6 SQLITE VB.NET Resource: own problem used for Codechef Snackdown Onsite