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.math.*;
import java.io.*; 
 public class B{
static int[] dx={-1,1,0,0};
static int[] dy={0,0,1,-1};
    static FastReader scan=new FastReader();
   public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
  static ArrayList<Pair>es;
  static LinkedList<Integer>edges[];
  static LinkedList<Integer>edges2[];

   static boolean prime[];
   static void sieve(int n) 
    { 
        
        prime = new boolean[n+1]; 
        for(int i=0;i<n;i++) 
            prime[i] = true; 
          
        for(int p = 2; p*p <=n; p++) 
        { 
           
            if(prime[p] == true) 
            { 
                
                for(int i = p*p; i <= n; i += p) 
                    prime[i] = false; 
            } 
        } 
          
        
    }      
     public static int lowerBound(long[] array, int length, long value) {
        int low = 0;
        int high = length;
        while (low < high) {
            final int mid = (low + high) / 2;
            //checks if the value is less than middle element of the array
            if (value <= array[mid]) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }
    public static int upperBound(long[] array, int length, long value) {
        int low = 0;
        int high = length;
        while (low < high) {
            final int mid = low+(high-low) / 2;
            if ( array[mid]>value) {
                high = mid ;
            } else {
                low = mid+1;
            }
        }
        return low;
    }
static long mod(long x,long y)
    {
        if(x<0)
            x=x+(-x/y+1)*y;
        return x%y;
    }    
     static boolean isPowerOfTwo(long n) 
    { 
        if (n == 0) 
            return false; 
  
        while (n != 1) { 
            if (n % 2 != 0) 
                return false; 
            n = n / 2; 
        } 
        return true; 
    } 

  
   
static boolean isprime(long x)
           {
            for(long i=2;i*i<=x;i++)
                if(x%i==0)
                    return false;
                return true;
           }


static int dist(int x1,int y1,int x2,int y2){
return Math.abs(x1-x2)+Math.abs(y1-y2);
}


    static long cuberoot(long x)
    {
        long lo = 0, hi = 1000005;
        while(lo<hi)
        {
            long m = (lo+hi+1)/2;
            if(m*m*m>x)
                hi = m-1;
            else
                lo = m;
        }
        return lo;
    }
     public static int log2(int N) 
    { 
  
        // calculate log2 N indirectly 
        // using log() method 
        int result = (int)(Math.log(N) / Math.log(2)); 
  
        return result; 
    } 
  
    
   
       static long gcd(long a, long b) {
    if(a!=0&&b!=0)
        while((a%=b)!=0&&(b%=a)!=0);
    return a^b;
}
    static long LCM(long a,long b){
    return (Math.abs(a*b))/gcd(a,b);
   }
   public static class comp1 implements Comparator<ArrayList<Integer>>{  
public int compare(ArrayList<Integer> o1,ArrayList<Integer> o2){
    if(o1.size()>0&&o2.size()>0&&o1.get(o1.size()-1)>o2.get(o2.size()-1))
        return 1;

 return -1;
}
  }
     public static class comp2 implements Comparator<Pair>{  
public int compare(Pair o1,Pair o2){
 
return (o2.ab-o1.ab)>0?1:-1;
}
  }
 static boolean can(int m,int s)
 {
    return (s>=0&&s<=m*9);
 }
   static boolean collinear(long x1, long y1, long x2,  
                          long y2, long x3, long y3) 
{
    long a = x1 * (y2 - y3) +  
                x2 * (y3 - y1) +  
                x3 * (y1 - y2); 
                if(a==0)
                    return true;
                return false;
}


static String gen(String s,int x)
{
    StringBuilder res=new StringBuilder("");
    for(int i=0;i<s.length();i++)
    {
        if(i+x<s.length()&&s.charAt(i+x)=='1')
            res.append("1");
        else if(i-x>=0&&s.charAt(i-x)=='1')
            res.append("1");
        else res.append("0");
    }
    return res.toString();
}
static StringBuilder tmp1,tmp2;
static void swap(int i,int j)
{
    char tmp=tmp1.charAt(i);
    tmp1.setCharAt(i,tmp1.charAt(j));
    tmp1.setCharAt(j,tmp);
     tmp=tmp2.charAt(i);
    tmp2.setCharAt(i,tmp2.charAt(j));
    tmp2.setCharAt(j,tmp);
}
static StringBuilder s,s2;
static StringBuilder res=new StringBuilder("");
static int LCS(int i,int j)
{
    if(i==s.length()||j==s2.length())
        return 0;
    if(s.charAt(i)==s2.charAt(j))
    {
        res.append(s.charAt(i));
        return LCS(i+1,j+1)+1;
    }
    int first=LCS(i+1,j);
    int second=LCS(i,j+1);
    //out.println(first);
    return Math.max(first,second);
}
static ArrayList<Pair>arr;
static long last,temp;
static boolean can(int i)
{
    //out.println(i);
    if(temp<=arr.get(i).x&&temp+arr.get(i).x-last>=arr.get(i).z){
        //if(i==1)
          // out.println("FUCK");
        return true;
    }
    else if(temp+arr.get(i).x-last>=arr.get(i).y&&temp+arr.get(i).x-last<=arr.get(i).z){
         //if(i==1)
          //      out.println("FUCK");
        return true;
    }
   else if(temp-arr.get(i).x-last>=arr.get(i).y&&temp-arr.get(i).x-last<=arr.get(i).z)
        
        {
           // if(i==2)
            //out.println("FUCK");
            return true;
        }
    //else if(temp>=arr.get(i).y&&temp<=arr.get(i).z)
      //  return true;
   // if(i==2)
     //   out.println("FUCK");
    return false;
    


}
public static void main(String[] args)  throws Exception 
{
    /*int xx=253;
    for(int i=1;i*i<=xx;i++)
    {
        if(xx%i==0)
        {
            System.out.println(i);
            System.out.println(xx/i);
        }
    }*/
//java.util.Scanner scan=new java.util.Scanner(new File("mootube.in"));
// PrintWriter out = new PrintWriter (new FileWriter("mootube.out"));
//scan=new FastReader("moocast.in");
//out = new PrintWriter ("moocast.out");
//System.out.println(3^2);
//System.out.println(19%4);
   //StringBuilder news=new StringBuilder("ab");
   //news.deleteCharAt(1);
   //news.insert(0,'c');
   //news.deleteCharAt(0);
   //System.out.println(news);
   //System.out.println(can(2,15));
    //System.out.println(LCM(2,2));
  // System.out.println(31^15);
 //System.out.println("");
   //System.out.println(824924296372176000L>(long)1e16);
int tt=1;
//rec(2020);
tt=scan.nextInt();
//int st=scan.nextInt();
//System.out.println(calc(91));
//sieve(21000);

//SNWNSENSNNSWNNW

   // System.out.println(set.remove(new Pair(1,1)));
//System.out.println(count("cccccccccccccccccccccccccooooooooooooooooooooooooodddddddddddddeeeeeeeeeeeeeeeeeeeeeeeeeffffffffffffforrrrrrrrrrrrrcesssssssssssss","codeforces"));
  //System.out.println(isPowerOfTwo(446265625L));
//System.out.println("daaa".compareTo("bccc"));
//System.out.println(2999000999L>1999982505L);
  outer:while(tt-->0)
 {
    int n=scan.nextInt();
    int arr[]=new int[n];
    int res=Integer.MAX_VALUE;
    boolean is=false,is2=false,canmid=false,canmax=false,canmin=false;

    int max=0,min=Integer.MAX_VALUE;
    for(int i=0;i<n;i++){
        arr[i]=scan.nextInt();
        if(i>0&&arr[i-1]!=-1&&arr[i]!=-1){
            if(res==Integer.MAX_VALUE)
        res=0;
            res=Math.max(Math.abs(arr[i]-arr[i-1]),res);
        }
            if(arr[i]==-1)
                is=true;
            if(arr[i]!=-1)
                is2=true;
            max=Math.max(arr[i],max);
            if(arr[i]!=-1)
            min=Math.min(arr[i],min);
    }
    //out.println(res);
   
    if(!is2)
    {
        out.println(0+" "+1);
        continue outer;
    }
    int l=0,r=max;
    int k=-1;
    while(l<=r)
    {
        int mid=(l+r)/2;
        int tmp[]=new int[n];
        int cur=0;
        for(int i=0;i<n;i++){
            if(arr[i]==-1)
                tmp[i]=mid;
            else
            tmp[i]=arr[i];
        }
        for(int i=1;i<n;i++)
        {
            cur=Math.max(cur,Math.abs(tmp[i]-tmp[i-1]));
        }
        if(cur<res){
            r=mid-1;
            res=cur;
            k=mid;
        }
        else l=mid+1;
    }
    //out.println(k);
    int tmp[]=new int[n];
    for(int i=0;i<n;i++)
    {
        if(arr[i]==-1)
            tmp[i]=max;
        else tmp[i]=arr[i];
    }
    int cur=0;
    for(int i=1;i<n;i++)
        {
            cur=Math.max(cur,Math.abs(tmp[i]-tmp[i-1]));
        }
        if(cur<=res){
            res=cur;
            k=max;
            canmax=true;
        }
        

     tmp=new int[n];
    for(int i=0;i<n;i++)
    {
        if(arr[i]==-1)
            tmp[i]=min;
        else tmp[i]=arr[i];
    }
    cur=0;
     for(int i=1;i<n;i++)
        {
            cur=Math.max(cur,Math.abs(tmp[i]-tmp[i-1]));
        }
          if(cur<=res){
            canmin=true;
            res=cur;
            k=min;
        }
        int mid=(min+max)/2;
         tmp=new int[n];
    for(int i=0;i<n;i++)
    {
        if(arr[i]==-1)
            tmp[i]=mid;
        else tmp[i]=arr[i];
    }
    cur=0;
     for(int i=1;i<n;i++)
        {
            cur=Math.max(cur,Math.abs(tmp[i]-tmp[i-1]));
        }
          if(cur<=res){
            canmid=true;
            res=cur;
            k=mid;
        }
       // out.println(k);
        if(k==-1){
            if(tt==10000-369)
                out.println(mid);
            res=Integer.MAX_VALUE;
            l=0;
            r=max;
             while(l<=r)
    {
         mid=(l+r)/2;
         tmp=new int[n];
         cur=0;
        for(int i=0;i<n;i++){
            if(arr[i]==-1)
                tmp[i]=mid;
            else
            tmp[i]=arr[i];
        }
        for(int i=1;i<n;i++)
        {
            cur=Math.max(cur,Math.abs(tmp[i]-tmp[i-1]));
        }
        if(cur<res){
            r=mid;
            res=cur;
            k=mid;
        }
        else l=mid+1;
    }
    tmp=new int[n];
    for(int i=0;i<n;i++)
        if(arr[i]==-1)
            tmp[i]=min;
        else tmp[i]=arr[i];
        cur=0;
        for(int i=1;i<n;i++)
        {
            cur=Math.max(cur,Math.abs(tmp[i]-tmp[i-1]));
        }
          if(cur<=res){
            //canmid=true;
            res=cur;
            k=min;
        }
        cur=0;
        tmp=new int[n];
    for(int i=0;i<n;i++)
        if(arr[i]==-1)
            tmp[i]=max;
        else tmp[i]=arr[i];
         for(int i=1;i<n;i++)
        {
            cur=Math.max(cur,Math.abs(tmp[i]-tmp[i-1]));
        }
          if(cur<=res){
            //canmid=true;
            res=cur;
            k=max;
        }
        cur=0;
          for(int i=0;i<n;i++)
        if(arr[i]==-1)
            tmp[i]=(max+min)/2;
        else tmp[i]=arr[i];
              for(int i=1;i<n;i++)
        {
            cur=Math.max(cur,Math.abs(tmp[i]-tmp[i-1]));
        }
            if(cur<=res){
            //canmid=true;
            res=cur;
            k=(max+min)/2;
        }
        
     
        }
        out.println(res+" "+k);

}


out.close();
}    


static class dsu{
    static int id[]=new int[101];
    dsu()
    {
        for(int i=0;i<101;i++)
            id[i]=i;
    }
    static int find(int x)
    {
        if(x==id[x])
            return x;
        return find(id[x]);
    }
    static void connect(int i,int j)
    {
        i=find(i);
        j=find(j);
        id[i]=j;
    }
    static boolean is(int i,int j)
    {
        return find(i)==find(j);
    }
}
static long binexp(long a,long n,long mod)
{
    if(n==0)
       return 1;
    long res=binexp(a,n/2,mod)%mod;
    res=res*res;
    if(n%2==1)
        return (res*a)%mod;
    else 
        return res%mod;
}
static class special{
    Pair x;
    Pair y;
    special(Pair x,Pair y)
    {
      this.x=new Pair(x.x,x.y);
      this.y=new Pair(y.x,y.y);
    }   
      @Override
        public int hashCode() {
            return (int)(x.x + 31 * y.y);
        }
        public boolean equals(Object other)
    {
        if(other instanceof special)
        {
            special e =(special)other;
            return this.x.x==e.x.x && this.x.y==e.x.y && this.y.x==e.y.x && this.y.y==e.y.y;
        }
        else return false;
    }
}
static long powMod(long base, long exp, long mod) {
       if (base == 0 || base == 1) return base;
       if (exp == 0) return 1;
       if (exp == 1) return base % mod;
       long R = powMod(base, exp/2, mod) % mod;
       R *= R;
       R %= mod;
       if ((exp & 1) == 1) {
           return base * R % mod;
       }
       else return R % mod;
   }
 public static  long pow(long b, long e) {
            long r = 1;
            while (e > 0) {
                if (e % 2 == 1) r = r * b ;
                b = b * b;
                e >>= 1;
            }
            return r;
        }

private static void sort(long[] arr) {
        List<Long> list = new ArrayList<>();
        for (long object : arr) list.add(object);
        Collections.sort(list);
        for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
    }
 public static class FastReader {
        BufferedReader br;
        StringTokenizer root;
        
 
        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        FastReader(String filename)throws Exception
        {

            br=new BufferedReader(new FileReader(filename));
        }
 
        String next() {
            while (root == null || !root.hasMoreTokens()) {
                try {
                    root = new StringTokenizer(br.readLine());
                } catch (Exception addd) {
                    addd.printStackTrace();
                }
            }
            return root.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
 
        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (Exception addd) {
                addd.printStackTrace();
            }
            return str;
        }
         public int[] nextIntArray(int arraySize) {
            int array[] = new int[arraySize];
 
            for (int i = 0; i < arraySize; i++) {
                array[i] = nextInt();
            }
 
            return array;
        }
}
public static class Pair implements Comparable<Pair>{
         long x;
         long y;
         long ab;
        
        long z;
        public Pair(){}
        public Pair(long x1, long y1,long z) {
            x=x1;
            y=y1;
            this.z=z;
        }
        public Pair(long x1, long y1) {
            x=x1;
            y=y1;
            this.ab=x+y;
        
        }
        @Override
        public int hashCode() {
            return (int)(x + 31 * y);
        }
        public String toString() {
            return x + " " + y;
        }
        @Override
        public boolean equals(Object o){
            if (o == this) return true;
            if (o.getClass() != getClass()) return false;
            Pair t = (Pair)o;
            return t.x == x && t.y == y;
        }
        public  int compareTo(Pair o)
        {
            return (int)(x-o.x);
        }
}

}







