A. Average of Intervals
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Given a sequence of length $$$n$$$, you need to select a number of mutually disjoint intervals from it such that the sum of the intervals divided by the number of intervals is maximized. Output the maximum value and the maximum number of intervals that can be selected in this case.

An interval can be obtained by deleting zero or more integers from the beginning and zero or more integers from the end of the sequence.

It can be shown that the answer can be expressed as an irreducible fraction $$$\frac{x}{y}$$$ where $$$x$$$ and $$$y$$$ are integers and $$$y \not\equiv 0\pmod{10^{18} + 9}$$$. Output the integer equal to $$$x\cdot y^{-1}\pmod {10^{18} + 9}$$$.

In other words, output such an integer $$$a$$$ that $$$0 \leq {a} \lt 10^{18} + 9$$$ and $$$a\cdot y \equiv x \pmod{10^{18} + 9}$$$.

Input

Each test contains multiple test cases. The first line contains a single integer t $$$(1\leq{t}\leq{10^6})$$$— the number of test cases. The description of the test cases follows.

The first line of each test case contains $$$1$$$ integer $$$n(1\leq{n}\leq{10^6})$$$.

The second line contains $$$n$$$ integers $$$a_1,a_2,a_3,...,a_n(-10^6\leq{a_i}\leq{10^6})$$$ representing the sequence.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$.

Output

For each test case, output the maximum value and the maximum number of intervals that can be selected in this case.

Example
Input
4
4
4 1 -5 3
3
1 -1 1
2
1 1
2
-1 -1
Output
5 1
1 2
2 1
1000000000000000008 2
Note

In the last test case, the optimal strategy is to choose the intervals [$$$1$$$,$$$1$$$] and [$$$2$$$,$$$2$$$]. The maximum value is $$$\frac{((-1)+(-1))}{2} = -1$$$ and two intervals are chosen .