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:
2
3
-1 -1 -1
4
2 0 -2 2 Output: -1 3
2 4

Constraints

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


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

hide comments
2016-08-09 18:32:38
Can be done in O(n) time and O(1) space without any casing :)
2015-12-16 17:58:27
Nice Problem!!learned many new thngs
2015-10-06 13:12:27
can somebody explain second test case . I think output should be : 2 3

Hi dear
i can :)
"2" , "2 0" , "2 0 -2 2 ", "2" !!!
2015-09-25 14:57:52
will brute force work ?
2015-08-28 01:28:29 (Tjandra Satria Gunawan)(曾毅昆)
<b>Finally AC</b> too many cases to handle, got a lot of WA *_*
2015-07-28 19:51:42 :.Mohib.:
Really Nice problem...!!
2015-06-22 16:12:53 thirupathireddy
is the complexity O(n)...?can anyone tell?
2015-06-07 11:52:38 CoNtRaDiCtIoN
awesome problem learnt something :)
2015-05-30 17:17:08 Garima
@Ankit Sultana: thankyou so much man! :D
2015-03-28 18:35:37 reddragon
can somebody explain second test case . I think output should be : 2 3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.