No submission language available for this problem.

Description

Input

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 10^4$)  — the number of test cases. The description of the test cases follows.

The first line of each test case contains one integer $n$ ($2 \leq n \leq 10^{5}$) — the size of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($-1 \leq a_i \leq 10 ^ {9}$). If $a_i = -1$, then the $i$-th integer is missing. It is guaranteed that at least one integer is missing in every test case.

It is guaranteed, that the sum of $n$ for all test cases does not exceed $4 \cdot 10 ^ {5}$.

Output

Print the answers for each test case in the following format:

You should print two integers, the minimum possible value of $m$ and an integer $k$ ($0 \leq k \leq 10^{9}$) that makes the maximum absolute difference between adjacent elements in the array $a$ equal to $m$.

Make sure that after replacing all the missing elements with $k$, the maximum absolute difference between adjacent elements becomes $m$.

If there is more than one possible $k$, you can print any of them.

Samples

7
5
-1 10 -1 12 -1
5
-1 40 35 -1 35
6
-1 -1 9 -1 3 -1
2
-1 -1
2
0 -1
4
1 -1 3 -1
7
1 -1 7 5 2 -1 5

1 11
5 35
3 6
0 42
0 0
1 2
3 4

Note

In the first test case after replacing all missing elements with $11$ the array becomes $[11, 10, 11, 12, 11]$. The absolute difference between any adjacent elements is $1$. It is impossible to choose a value of $k$, such that the absolute difference between any adjacent element will be $\leq 0$. So, the answer is $1$.

In the third test case after replacing all missing elements with $6$ the array becomes $[6, 6, 9, 6, 3, 6]$.

• $|a_1 - a_2| = |6 - 6| = 0$;
• $|a_2 - a_3| = |6 - 9| = 3$;
• $|a_3 - a_4| = |9 - 6| = 3$;
• $|a_4 - a_5| = |6 - 3| = 3$;
• $|a_5 - a_6| = |3 - 6| = 3$.

So, the maximum difference between any adjacent elements is $3$.