Time Limit:10000ms Memory Limit:65536KB

Description

When baihacker's girl friend hy's birthday comes, baihacker give her a circinate
cake, which is divided into n equal units. hy gives each unit a score according
how she likes the unit.hy wants to select a continue sequence unit of the cake
such that the sum of the score of the units is maximized, how many ways to
achieve the goal?

Input

The first line of input is an integer T which stands for the number of test cases.
Each test case contains two lines.
The first line is a integer n.
The second is n integers seperated by a space and the. The ith integer stands for
the score of the ith unit when we count the units from 1 to n in an anticlockwise
order where the first unit is optional.
1<=n<=100,000
The absolute of the integers in the second line is no more than 1,000,000,000

Output

For each test case output the answer in a single line which contains two integers
seperated by a space.The first one is the maximized score and the second is the
number of ways to achieve the goal.

Sample Input

4
1
1
1
0
2
0 0
2
-1 -1

Sample Output

1 1
0 1
0 3
-1 2

Hint


Author

baihacker

Source

Preliminary (Single)