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.*;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.security.KeyStore.Entry;
import java.text.DecimalFormat;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import javax.net.ssl.SSLContext;

public class Main
{ 
   //static long mod=(long)(1e+9 + 7);
   static long mod=(long)998244353;
   
   static int[] sieve;
   static ArrayList<Integer> primes;
   static long min=Long.MAX_VALUE;
   
   public static void main(String[] args) throws java.lang.Exception
   {	  	
	     fast s = new fast();
	     PrintWriter out=new PrintWriter(System.out);
	     
	     int t=s.nextInt();
	    
	     StringBuilder fans=new StringBuilder("");
	     
	     while(t>0)
	    	 {
	    		 int n=s.nextInt();
	    		 long a[]=new long[n];
	    		 
	    		 for(int i=0;i<n;i++) a[i]=s.nextLong();
	    		 
	    		 ArrayList<Long> arr=new ArrayList<Long>();
	    		 HashSet<Long> hm=new HashSet<Long>();
	    		 
	    		 for(int i=0;i<n;i++)
	    			 {
	    				 if(a[i]!=-1)
	    					 {
	    						 if((i-1)>=0 && a[i-1]==-1) hm.add(a[i]);
	    						 if((i+1)<n && a[i+1]==-1) hm.add(a[i]);
	    					 }
	    			 }
	    		 
	    		 long sum=0;
	    		 for(long fk:hm) {sum+=fk;arr.add(fk);}
	     
	    		 Collections.sort(arr);
	    		 int x=arr.size()-1;
	    		 
	    		 long k=0;
                 long ans=0;
	    		 
	    		 if(arr.size()%2==1 && arr.size()>0)
	    			 {
	    		         k=arr.get(x/2).longValue();
	    	    		 for(int i=0;i<n;i++)
	    	    			 {
	    	    				 if(a[i]==-1) a[i]=k;
	    	    			 }
	    	    		 for(int i=1;i<n;i++)
	    	    			 {
	    	    				 ans=Math.max(ans,(long)Math.abs(a[i]-a[i-1]));
	    	    			 }
	    			 }
	    		 else if(arr.size()%2==0 && arr.size()>0)
	    			 {
	    			     long k1=(arr.get(x/2).longValue()+arr.get(x/2+1).longValue())/2;
	    			     long k2=Math.min((long)1000000000, k1+1);
	    			     
	    			     long ans1=0;
	    			     long ans2=0;
	    			     ////////////////////////////
	    			     long b[]=new long[n];
	    			     for(int i=0;i<n;i++) b[i]=a[i];
	    			     for(int i=0;i<n;i++)
	    	    			 {
	    	    				 if(b[i]==-1) b[i]=k1;
	    	    			 }
	    			     for(int i=1;i<n;i++)
	    	    			 {
	    	    				 ans1=Math.max(ans1,(long)Math.abs(b[i]-b[i-1]));
	    	    			 }
	    			     
	    			     /////////////
	    			     for(int i=0;i<n;i++) b[i]=a[i];
	    			     for(int i=0;i<n;i++)
	    	    			 {
	    	    				 if(b[i]==-1) b[i]=k2;
	    	    			 }
	    			     for(int i=1;i<n;i++)
	    	    			 {
	    	    				 ans2=Math.max(ans2,(long)Math.abs(b[i]-b[i-1]));
	    	    			 }
	    			     
	    			     if(ans1<ans2) {ans=ans1;k=k1;}
	    			     else {ans=ans2;k=k2;}
	    			 }
	    		 
	    		 long ans4=Long.MAX_VALUE;
	    		 
	    		 if(arr.size()>0)
	    			 {
			    		 sum/=arr.size();
			    		 for(int i=0;i<n;i++)
			    			 {
			    				 if(a[i]==-1) a[i]=sum;
			    			 }
			    		 for(int i=1;i<n;i++)
			    			 ans4=Math.max(ans4, a[i]-a[i-1]);
			    		 
			    		 if(ans4<ans) {ans=ans4;k=sum;}
	    			 }
	    		 
	    		 fans.append(String.valueOf(ans)+" "+String.valueOf(k)+"\n");
	    		 t--;
	    	 }
	     System.out.println(fans);
   }
  
 
 
static class fast {   
	    private InputStream i;
		private byte[]  buf = new byte[1024];
		private int curChar;
		
		private int numChars;
		
		//Return floor log2n
		public static long log2(long bits) // returns 0 for bits=0
			{
			    int log = 0;
			    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
			    if( bits >= 256 ) { bits >>>= 8; log += 8; }
			    if( bits >= 16  ) { bits >>>= 4; log += 4; }
			    if( bits >= 4   ) { bits >>>= 2; log += 2; }
			    return log + ( bits >>> 1 );
			}
		
		public static boolean next_permutation(int a[])
		   {
			   int i=0,j=0;int index=-1;	   
			   int n=a.length;
			   
			   for(i=0;i<n-1;i++)
				   if(a[i]<a[i+1]) index=i;
			   
			   if(index==-1) return false;
			   i=index;
 
			  
			   for(j=i+1;j<n && a[i]<a[j];j++);
 
			   int temp=a[i];
			   a[i]=a[j-1];
			   a[j-1]=temp;
			   	   
			   for(int p=i+1,q=n-1;p<q;p++,q--)
			   {
				   temp=a[p];
				   a[p]=a[q];
				   a[q]=temp;
			   }
			   
			   return true;
		   }
		   
		   
		public static void division(char ch[],int divisor)
		   {
			   int div=Character.getNumericValue(ch[0]); int mul=10;int remainder=0;
			   StringBuilder quotient=new StringBuilder("");
			   for(int i=1;i<ch.length;i++)
			   {
				   div=div*mul+Character.getNumericValue(ch[i]);	
				   if(div<divisor) {quotient.append("0");continue;}
				   quotient.append(div/divisor);
				   div=div%divisor;mul=10;
				   
			   } 
			   remainder=div;
			   while(quotient.charAt(0)=='0')quotient.deleteCharAt(0);	   
			   System.out.println(quotient+" "+remainder);	  
		   }
		
		public static void sieve(int size)
		{
			sieve=new int[size+1];
			
			primes=new ArrayList<Integer>();
			
			sieve[1]=1;
			
			for(int i=2;i*i<=size;i++)
			{
				if(sieve[i]==0)
				 {
					for(int j=i*i;j<size;j+=i) {sieve[j]=1;}
				 }
			}
			
			for(int i=2;i<=size;i++)
			{
				if(sieve[i]==0) primes.add(i);
			}
		}
		
		public static long pow(long n, long b, long MOD)
		   {
		       long x=1;long y=n; 
		       while(b > 0)
		       {
		           if(b%2 == 1)
		           {
		               x=x*y;
		               if(x>MOD) x=x%(MOD);
		           }
		           y = y*y;
		           if(y>MOD) y=y%(MOD); 
		           b >>= 1;
		       }
		       return x;
		   }
 
 
		public static long mod_inv(long n,long mod)
		{
			return pow(n,mod-2,mod);
		}
		
		//Returns index of highest number less than or equal to key
		 public static int upper(long[] a,int length,long key)
		 {
			    int low = 0;
		        int high = length-1;
		        int ans=-1;
		        
		        while (low <= high) {
		            int mid = (low + high) / 2;
		            if (key >= a[mid]) {
		                ans=mid;
		            	low = mid+1;
		            } else if(a[mid]>key){
		                high = mid - 1;
		            }
		        }
		        return ans;
		}
		
		//Returns index of least number greater than or equal to key
		 public static int lower(long[] a,int length,long key)
		 {
			    int low = 0;
		        int high = length-1;
		        int ans=-1;
		        
		        while (low <= high) {
		            int mid = (low + high) / 2;
		            if (key<=a[mid]) {
		                ans=mid;
		            	high = mid-1;
		            }
		            else{
		            		low=mid+1;
		            	}
		        }
		        return ans;
		} 
		   
		public long gcd(long r,long ans)
		{
			if(r==0) return ans;
			return gcd(ans%r,r);
		}
		public fast() {
			this(System.in);
		}
		public fast(InputStream is) {
			i = is;
		}
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = i.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
		public String nextString() {
     		int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
 
	}	
}