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.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.util.InputMismatchException;

public class Solution 
{
	static InputReader in = new InputReader(System.in);
	static int mod = (int)1e9 + 7;
	static int MAXN = 100005;
	static long[] fact = new long[MAXN];
	static long[] inv = new long[MAXN];
	
    public static void main(String args[]) {
        new Thread(null, new Runnable() {
            public void run() {
                try{
                    solve();
                }
                catch(Exception e){
                    e.printStackTrace();
                }
            }
        }, "1", 1 << 26).start();
    }
    
    public static void solve(){
    	int t = in.ni();
    	while(t-- > 0) {
    		int n = in.ni();
    		int[] ar = intArray(n);
    		int max = Integer.MIN_VALUE;
    		int min = Integer.MAX_VALUE;
    		for(int i = 0; i < n; i++) {
    			if(ar[i] == -1) {
    				if(i != 0 && ar[i - 1] != -1) {
    					max = Math.max(max, ar[i - 1]);
    					min = Math.min(min, ar[i - 1]);
    				} 
    				if(i != n - 1 && ar[i + 1] != -1) {
    					max = Math.max(max, ar[i + 1]);
    					min = Math.min(min, ar[i + 1]);    					
    				}
    			}
    		}
    		
    		int k = (max + min)/2;
    		long res = 0;
    		for(int i = 0; i < n; i++) if(ar[i] == -1) ar[i] = k;
    		for(int i = 1; i < n; i++) {
    			res = Math.max(res, Math.abs(ar[i] - ar[i - 1]));
    		}
    		pn(res + " " + (max + min)/2);
    	}
    }
   
    /*TEMPLATE*/
    
    //MATHS
    static int max(Integer... ar) {
    	int max = Integer.MIN_VALUE;
    	for(int i: ar) {
    		max = Math.max(max, i);
    	}
    	return max;
    }
    
    static long max(Long... ar) {
    	long max = Integer.MIN_VALUE;
    	for(long i: ar) {
    		max = Math.max(max, i);
    	}
    	return max;
    }
  
    static int gcd(int a, int b) {
    	return (b==0)?a:gcd(b,a%b);
    }
    
    static long binPow(long x, long y) {
        long ans = 1L;
        while(y > 0) {
            if(y % 2 == 1)
                ans = mul(ans, x);
            x = mul(x, x);
            y /= 2;
        }
        return ans;
    }
    
    static long add(long x, long y) {
    	x += y;
    	return mod(x, mod);
    }
    
    static long mul(long x, long y) {
    	return mod(x * y, mod);
    }
    
    static long divide(long x, long y) {
        return mul(x, binPow(y, mod - 2));
    }

    static long mod(long x, long p) {
        x %= p;
        if (x < 0)
            x += p;
        return x;
    }
        
    public static int[] spf(int maxn) {
    	int[] spf=new int[maxn+1];
    	spf[0]=spf[1]=1;
    	for(int i=2;i<=maxn;i++) {
    		if(i%2==0) spf[i]=2;
    		else 
    			spf[i]=i;
    	}
    	for(int i=3;i*i<=maxn;i++) {
    		if(spf[i]==i){
    			for (int j=i*i; j<=maxn; j+=i) 
                    if (spf[j]==j) 
                        spf[j] = i;
    		}
    	}
    	return spf;
    }
    
    static void nCrInit() {
    	fact[0] = 1;
    	for(int i = 1; i < MAXN; i++) fact[i] = mul(fact[i - 1], 1L * i);
    	inv[MAXN - 1] = binPow(fact[MAXN - 1], mod - 2); 
    	for(int i = MAXN - 2; i >= 0; i--) inv[i] = mul(inv[i + 1], 1L * (i + 1));
     }
    
    static long nCr(int n, int r) {
    	if(r > n || n < 0 || r < 0) return 0;
    	return fact[n] * inv[r] % mod * inv[n - r] % mod;
    }
    
    //ARRAYS
    public static int[] intArray(int n) {
    	int ar[]=new int[n];
    	for(int i=0;i<n;i++)
    		ar[i]=in.nextInt();
    	return ar;
    }
    
    public static void swap(int i, int j, int ar[]) {
    	int c=ar[i];ar[i]=ar[j];ar[j]=c;
    }
    
    public static void reverse(int ar[]) {
    	int l=0, r=ar.length-1;
    	while(l<r) {
    		int temp=ar[l]; ar[l]=ar[r]; ar[r]=temp;
    		l++; r--;
    	}
    }
    
    static int max(int[] ar) {
    	int max = Integer.MIN_VALUE;
    	for(int i: ar) {
    		max = Math.max(max, i);
    	}
    	return max;
    }
    
    static long max(long[] ar) {
    	long max = Integer.MIN_VALUE;
    	for(long i: ar) {
    		max = Math.max(max, i);
    	}
    	return max;
    }
    
    public static int upperBound(int[] array, int value) {
    	//return next higher element. If greater than all elements then returns array.length
    	//returns 0 if smaller than all elements
    	int low = 0;
    	int high = array.length;
    	while (low < high) {
    		final int mid = (low + high) / 2;
    		if (value >= array[mid]) {
    			low = mid + 1;
    		} else {
    			high = mid;
    		}
    	}
    	return low;
    }
    
    public static int lowerBound(int[] array, int value) {
    	//Returns first occurrence.
    	//Bigger than all elements then return array.length
    	//Not found, then next greater.s
    	int low = 0;
    	int high = array.length;
    	while (low < high) {
    		final int mid = (low + high) / 2;
			if (value <= array[mid]) {
			high = mid;
			} else {
				low = mid + 1;
			}
    	}
    	return low;
	}
    
    //Segment Tree
    static class SegNode {
    	//SegNode contains all query variables
    	long v;
    	SegNode() {
    		//Initialise using identity values
    		v = Integer.MIN_VALUE;
    	}
    	
    	SegNode(long v) {
    		this.v = v;
    	}
    	
    	public void merge(SegNode l, SegNode r) {
    		this.v = Math.max(l.v, r.v);
    	}
    }
    
    static class SegUpdate {
    	//It contains only the updates not the query variables.
    	long v; 
    	SegUpdate() {
    		//Initialise all segupdate variables here with identity values
    		// 0 for sum
    		//Integer.MAX_VALUE for min operations
    		// 1 for product, etc.
    		this.v = 0;
    	}
    	
    	SegUpdate(long v) {
    		this.v = v;
    	}
    	
    	//Combine current update with other update.
    	//Other update is newer than my present update
    	//In case of non-lazy propagation leave this blank
    	public void combine(SegUpdate other, int tl, int tr) {
    	}
    	
    	//Apply all updates so far in the query variables inside SegNode
    	//In case of non-lazy updates, consider x to be a leaf node.
    	public void apply(SegNode x, int tl, int tr) {
    		x.v = v;
    	}
    }
    
    static class SegTree {
    	int len;
    	SegNode[] t;
    	SegUpdate[] u;
    	boolean[] lazy;
    	
    	SegTree(int l){
    		len = l;
    		t = new SegNode[4 * len];
    		for(int i = 0; i < t.length; i++) t[i] = new SegNode();
    		u = new SegUpdate[4 * len];
    		for(int i = 0; i < u.length; i++) u[i] = new SegUpdate();    		
    		lazy = new boolean[4 * len];
    	}
    	
    	int descent(int x, int l) {
    		return descent(1, 0, len - 1, x, l);
    	}
    	
    	int descent(int v, int tl, int tr, int x, int l) {
    		pn(x+" "+l);
    		while(tl != l) {
    			pn(tl+" "+tr);
    			int tm = (tl + tr) >> 1;
    			if(l < tm) {
    				tr = tm - 1;
    				v = 2*v;
    			} else {
    				tl = tm;
    				v = 2*v + 1;
    			}
    		}
    		
    		if(t[v].v < x) {
    			return -1;
    		} 
    		
    		while(tl < tr) {
    			int tm = (tl + tr)/2;
    			if(t[2*v].v >= x) {
    				tr = tm;
    				v = 2*v;
    			} else {
    				tl = tm + 1;
    				v = 2*v + 1;
    			}
    		}
			return tl;
    	}
     
    	void pushdown(int v, int tl, int tr){
    		if(!lazy[v]) return;
    		int tm = (tl + tr) >> 1;
    		apply(v<<1, tl, tm, u[v]);
    		apply(v<<1|1, tm + 1, tr, u[v]);
    		u[v] = new SegUpdate();
    		lazy[v] = false;
    	}
     
    	void apply(int v, int tl, int tr, SegUpdate upd){
    		if(tl != tr){
    			lazy[v] = true;
    			u[v].combine(upd, tl, tr);
    		}
    		upd.apply(t[v], tl, tr);
    	}
    	
    	private void build(int[] arr, int v, int tl, int tr){
    		if(tl == tr){
    			t[v] = new SegNode(arr[tl]);
    			return;
    		}
    		int tm = (tl + tr) >> 1;
    		build(arr, v<<1, tl, tm);
    		build(arr, v<<1|1, tm + 1, tr);
    		t[v].merge(t[v<<1], t[v<<1|1]);
    	}
     
    	private SegNode query(int v, int tl, int tr, int l, int r){
    		if(l > tr || r < tl){
    			return new SegNode();
    		}
    		if(tl >= l && tr <= r){
    			return t[v];
    		}
    		pushdown(v, tl, tr);
    		int tm = (tl + tr) >> 1;
    		SegNode a = query(v<<1,tl,tm,l,r),b = query(v<<1|1,tm+1,tr,l,r);
    		SegNode ans = new SegNode();
    		ans.merge(a,b);
    		return ans;
    	}
     
    	// rupd = range update
    	private void rupd(int v, int tl, int tr, int l, int r, SegUpdate upd){
    		if(l > tr || r < tl){
    			return;
    		}
    		if(tl >= l && tr <= r){
    			apply(v,tl,tr,upd);
    			return;
    		}
    		pushdown(v,tl,tr);
    		int tm = (tl + tr) >> 1;
    		rupd(v<<1,tl,tm,l,r,upd);
    		rupd(v<<1|1,tm+1,tr,l,r,upd);
    		t[v].merge(t[v<<1], t[v<<1|1]);
    	}
     
    	void build(int[] arr){
    		build(arr, 1, 0, len - 1);
    	}
    	
    	void build(long[] arr){
    		build(arr, 1, 0, len - 1);
    	}
    	
    	private void build(long[] arr, int v, int tl, int tr){
    		if(tl == tr){
    			t[v] = new SegNode(arr[tl]);
    			return;
    		}
    		int tm = (tl + tr) >> 1;
    		build(arr, v<<1, tl, tm);
    		build(arr, v<<1|1, tm + 1, tr);
    		t[v].merge(t[v<<1], t[v<<1|1]);
    	}
    	
    	SegNode query(int l, int r){
    		return query(1,0,len-1,l,r);
    	}
    	
    	void rupd(int l, int r, SegUpdate upd){
    		rupd(1,0,len-1,l,r,upd);
    	}
    	
    	void debug() { 
    		System.out.println("------Debug-----");
    		for(int i = 0; i < 4 * len; i++) {
        		System.out.print(t[i].v+" ");
        	}
    		
    		for(int i = 0; i < 4 * len; i++) {
        		System.out.print(u[i].v+" ");
        	}
    		
        	System.out.println();
        	System.out.println(Arrays.toString(lazy));
        	System.out.println("-------------");
    	}
    }
   
    public static void pn(Object o) {
      System.out.println(o);
    }
    
    static class InputReader {
 
        private InputStream stream;
        private byte[] buf = new byte[8192];
        private int curChar;
        private int snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream) {
            this.stream = stream;
        }
 
        public int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
 
            int res = 0;
 
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
 
            return res * sgn;
        }
        
        public int ni() {
        	return nextInt();
        }
 
        public long nextLong() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
 
            long res = 0;
 
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
 
            return res * sgn;
        }
        
        public long nl() {
        	return nextLong();
        }
 
        public String readString() {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}