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 ≤ k ≤ 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 ≤ i ≤ 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 ≤ t ≤ 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 ≤ n ≤ 10^{5}) — the size of the array a.

The second line of each test case contains n integers a_1, a_2, …, a_n (-1 ≤ a_i ≤ 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 ⋅ 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 ≤ k ≤ 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 ≤ 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.
import java.util.*;
import java.io.*;
import java.math.BigInteger;
 public class Solution
{
     static class Pair<A,B>{
        A parent;
        B rank;
        Pair(A parent,B rank)
        {
            this.rank=rank;
            this.parent=parent;
        }
    }
//    static int find(Pair pr[],int i)
//    {
//        if(i==pr[i].parent)
//            return i;
//        else
//        {
//            pr[i].parent=find(pr,pr[i].parent);
//            return pr[i].parent;
//        }
//    }
//    static void join(Pair[] pr,int i,int j)
//    {
//        i=find(pr,i);
//        j=find(pr,j);
//        if(i==j)
//            return;
//        if(pr[i].rank>=pr[j].rank)
//        {
//            pr[j].parent=i;
//            pr[i].rank+=pr[j].rank;
//        }
//        else
//        {
//            pr[i].parent = j;
//            pr[j].rank+=pr[i].rank;
//        }
//    }
    static void swap(char ar[],int i,int j)
    {
        char f = ar[i];
        ar[i]=ar[j];
        ar[j]=f;
    }
    static ArrayList<Integer> graph[] ;
    static TreeSet<Long> ts;
    public static void main (String[] args) throws IOException
    {
        StringBuilder sb = new StringBuilder();
        FastReader s1 = new FastReader();
        int t=s1.I();
        while(t--!=0)
        {
            int n=s1.I();
            long ar[] = new long[n];
            for(int i=0;i<n;i++)
            {
                ar[i]=s1.L();
            }
            long min=Long.MAX_VALUE;
            long max=Long.MIN_VALUE;
            for(int i=0;i<n;i++)
            {
                if(ar[i]==-1)
                {
                    if(i>0)
                    {
                        if(ar[i-1]<min && ar[i-1]!=-1)
                        {
                            min=ar[i-1];
                        }
                        if(ar[i-1]>max && ar[i-1]!=-1)
                            max=ar[i-1];
                       
                    }
                    if(i<n-1)
                    {
                        if(ar[i+1]<min && ar[i+1]!=-1)
                        {
                            min=ar[i+1];
                        }
                        if(ar[i+1]>max && ar[i+1]!=-1)
                            max=ar[i+1];
                    }
                }
            }
            
            if(min==Long.MAX_VALUE || max==Long.MIN_VALUE)
            {
                max=min=1000000000;
            }
            long mid=(min+max)/2;
//            System.out.println(min+" "+max);
            long temp=Math.max(Math.abs(min-mid), Math.abs(max-mid));
            for(int i=0;i<n;i++)
            {
                if(ar[i]==-1)
                    ar[i]=mid;
                if(i>0)
                {
                    if(Math.abs(ar[i]-ar[i-1])>temp)
                    {
                        temp=Math.abs(ar[i]-ar[i-1]);
                    }
                }
            }
            sb.append(temp+" "+mid+"\n");
        }
        System.out.println(sb);
    }
    static boolean add(HashSet<Character> hs,char value)
    {
        if(hs.contains(value))
            {
                return true;
            }
        if(hs.size()<2)
        {
            hs.add(value);
            return true;
        }
        else
        {
                return false;
        }
    }
    static int dayofweek(long d, int m, long y) 
{ 
    int t[] = { 0, 3, 2, 5, 0, 3, 5, 1, 4, 6, 2, 4 }; 
    y -= (m < 3) ? 1 : 0; 
    return (int)( y + y/4 - y/100 + y/400 + t[(m-1)] + d) % 7; 
}
        static String preprocess(String s)
    {
        StringBuilder sb = new StringBuilder();
        sb.append("@#");
        for(int i=0;i<s.length();i++)
        {
            sb.append(s.charAt(i)).append("#");
        }
        sb.append("$");
        return sb.toString();
    }
    static String LPS(String s)
    {
        String snew = preprocess(s);
        int n = snew.length();
//        System.out.println(snew);
        int c = 0,r = 0;
        int maxlen = 0;
        int index=0;
        int len[] = new int[n];
        for(int i=1;i<n-1;i++)
        {
            int mirr = c-(i-c);
            if(i<r)
            {
                len[i]=Math.min(len[mirr],r-i);
            }
      //      System.out.println(i+" ");
            while(snew.charAt(i+len[i])==snew.charAt(i-len[i]))
                len[i]++;
            if(i+len[i]>r)
            {
                c = i;
                r = i+len[i];
            }
//            System.out.println(c+" "+i+" "+snew.charAt(i)+" "+len[i]+" "+maxlen+" "+index);
            if(len[i]>maxlen)
            {
//                System.out.println("inside");
                maxlen = len[i];
                index = i;
            }
        }
        maxlen--;
        int left = (index-maxlen-1)/2;
        int right = left+maxlen;
        return s.substring(left, right);
    }
    static long phi(long n)
    {
        long result=n;
        for(int i=2;i<=Math.sqrt(n);i++)
        {
            if(n%i==0)
            {
                result-=result/i;
            }
            while(n%i==0)
            {
                n=n/i;
            }
        }
        if(n>1)
        {
            result-=(result/n);
        }
        return result;
    }
    static ArrayList<Integer> primeFactor(int n)
    {
        ArrayList<Integer> ans = new ArrayList<>();
        if(n%2==0)
            ans.add(2);
        while (n%2==0)
        {   
            n /= 2;
        }
        for (int i = 3; i <= Math.sqrt(n); i+= 2)
        {
            if(n%i==0)
                ans.add(i);
            while (n%i == 0)
            {
                n /= i;
            }
        }
        if (n > 2)
            ans.add(n);
        return ans;
    }
    static int longestSubSeg(int a[], int n,int k)
    {
        int cnt0 = 0;
        int l = 0;
        int max_len = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == 0)
                cnt0++;
            while (cnt0 > k) {
                if (a[l] == 0)
                    cnt0--;
                l++;
            }
            max_len = Math.max(max_len, i - l + 1);
        }
        
        return max_len;
    }
    static void dfs(int index,boolean ar[])
    {
        ar[index]=true;
        for(int i=0;i<graph[index].size();i++)
        {
            if(!ar[graph[index].get(i)])
            {
                dfs(graph[index].get(i),ar);
            }
        }
    }
    static int binary(int left,int right,int ar[],int no)
    {
        int mid=(left+right)/2;
        if(Math.abs(right-left)<=1)
        {
            if(no>=ar[right])
            {
                return right+1;
            }
            else if(no<ar[left])
            {
                return left;
            }
            else
            {
                return left+1;
            }
        }
        if(ar[mid]>no)
        {
            right=mid-1;
            return binary(left, right, ar, no);
        }
        else{
            left=mid;
            return binary(left, right, ar, no);
        }
    }
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader()
        {
            br = new BufferedReader(new
                             InputStreamReader(System.in));
        }
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
        
        int I()
        {
            return Integer.parseInt(next());
        }
        
        long L()
        {
            return Long.parseLong(next());
        }
        
        double D()
        {
            return Double.parseDouble(next());
        }
        
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
    static long gcd(long a,long b)
    {
        if(a%b==0)
            return b;
        return gcd(b,a%b);
    }
    static float power(float x, int y)
    {
        float temp;
        if( y == 0)
            return 1;
        temp = power(x, y/2);
        
        if (y%2 == 0)
            return temp*temp;
        else
        {
            if(y > 0)
                return x * temp * temp;
            else
                return (temp * temp) / x;
        }
    }
    static long pow(long x, long y)
    {
        int p = 1000000007;
        long res = 1;
        x = x % p;
        while (y > 0)
        {
            if((y & 1)==1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }
    static ArrayList<Integer> sieveOfEratosthenes(int n)
    {
        ArrayList<Integer> arr=new ArrayList<Integer>();
        boolean prime[] = new boolean[n+1];
        for(int i=2;i<n;i++)
            prime[i] = true;
        
        for(int p = 2; p*p <=n; p++)
        {
            if(prime[p] == true)
            {
                arr.add(p);
                for(int i = p*p; i <= n; i += p)
                    prime[i] = false;
            }
        }
        return arr;
    }
}
