Dark is going to attend Motarack's birthday. Dark decided that the gift he is going to give to Motarack is an array $a$ of $n$ non-negative integers.

Dark created that array $1000$ years ago, so some elements in that array disappeared. Dark knows that Motarack hates to see an array that has two adjacent elements with a high absolute difference between them. He doesn't have much time so he wants to choose an integer $k$ ($0 \leq k \leq 10^{9}$) and replaces all missing elements in the array $a$ with $k$.

Let $m$ be the maximum absolute difference between all adjacent elements (i.e. the maximum value of $|a_i - a_{i+1}|$ for all $1 \leq i \leq n - 1$) in the array $a$ after Dark replaces all missing elements with $k$.

Dark should choose an integer $k$ so that $m$ is minimized. Can you help him?


-----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.


-----Example-----
Input
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

Output
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$.

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
    n=int(input())
    a=list(map(int,input().split()))
    ans,small,big=0,2*10**9,-1
    for i in range(len(a)-1):
        if a[i]==-1 and a[i+1]!=-1:
            small=min(small, a[i+1])
            big=max(big, a[i+1])
        if a[i]!=-1 and a[i+1]==-1:
            small = min(small, a[i])
            big = max(big, a[i])
        if a[i]!=-1 and a[i+1]!=-1:
            ans=max(ans, abs(a[i]-a[i+1]))
    if big==-1:print(ans, 0)
    else:
        x=(small+big)//2
        ans=max(ans, abs(big-x))
        ans=max(ans, abs(x-small))
        print(ans, x)

for _ in range(int(input())):
    n = int(input())
    ans = 0
    adj = []
    a = tuple(map(int, input().split()))
    a1 = iter(a)
    next(a1)
    for ai, aj in zip(a, a1):
        if ai > -1 < aj:
            ans = max(ans, abs(ai - aj))
        elif ai != aj:
            adj.append(ai + aj + 1)
    min_adj, max_adj = (min(adj), max(adj)) if adj else (0, 0)
    print(max(ans, (max_adj - min_adj + 1) // 2), (min_adj + max_adj) // 2)


import sys
input = sys.stdin.readline

t=int(input())
for test in range(t):
    n=int(input())
    A=list(map(int,input().split()))

    MAX=0
    DIFMIN=10**10
    DIFMAX=-100

    for i in range(1,n):
        if A[i-1]==A[i]==-1:
            continue
        elif A[i-1]==-1:
            DIFMIN=min(DIFMIN,A[i])
            DIFMAX=max(DIFMAX,A[i])
        elif A[i]==-1:
            DIFMIN=min(DIFMIN,A[i-1])
            DIFMAX=max(DIFMAX,A[i-1])
        else:
            MAX=max(MAX,abs(A[i]-A[i-1]))

    
    if DIFMIN==10**10:
        print(0,0)
    else:
        #print(DIFMIN,DIFMAX)
        k=(DIFMAX+DIFMIN)//2
        m=max(MAX,DIFMAX-k,k-DIFMIN)

        print(m,k)


from math import *

zzz = int(input())
for zz in range(zzz):
    n = int(input())
    a = [int(i) for i in input().split()]
    b = set()
    for i in range(n):
        if a[i] == -1:
            if i > 0:
                if a[i-1] >= 0:
                    b.add(a[i-1])
            if i < n - 1:
                if a[i+1] >= 0:
                    b.add(a[i+1])
    b = list(b)
    if len(b) == 0:
        print(0, 0)
    else:
        k = (min(b) + max(b)) // 2
        m = 0
        for i in range(n):
            if a[i] == -1:
                a[i] = k
        for i in range(1, n):
            m = max(m, abs(a[i-1]- a[i]))
        print(m, k)