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.
/* package codechef; // don't place package name! */

import java.util.*;
import java.io.*;
import java.math.*;

/* Name of the class has to be "Main" only if the class is public. */
public class Main
{
	
	public static void main (String[] args) throws IOException
	{
		  Reader s=new Reader();
		  BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		  PrintWriter pt=new PrintWriter(System.out);
		  int T=s.nextInt();
		  while(T-->0)
		  {
			  int n=s.nextInt();
			  long arr[]=new long[n];
			  long sum=0,k=0;
			  for(int i=0;i<n;i++) {
				  arr[i]=s.nextLong();
				  if(arr[i]==-1)
					  k++;
			  }
			  long max=Long.MIN_VALUE;
			  long min=Long.MAX_VALUE;
			  for(int i=1;i<n-1;i++)
			  {
				  if(arr[i]!=-1&& (arr[i-1]==-1|| arr[i+1]==-1)) {
					  max=Math.max(max, arr[i]);
					  min=Math.min(min, arr[i]);
				  }
			  }
			  if(arr[0]!=-1&&arr[1]==-1)
			  {
				  max=Math.max(max, arr[0]);
				  min=Math.min(min, arr[0]);
			  }
			  if(arr[n-1]!=-1&&arr[n-2]==-1)
			  {
				  max=Math.max(max, arr[n-1]);
				  min=Math.min(min, arr[n-1]);
			  }
			  if(k==n) {
				  pt.println("0 0");
				  continue;
			  }
			  
			  long m=(max+min)/2;
			  
			  replace(arr, m);
			  
			  long ma=maxabs(arr);
			  
			  
			  pt.println(ma+" "+(m));
			  
			  
		  }
		pt.close();
	}
	static long maxabs(long[] arr)
	{
		long max=Integer.MIN_VALUE;
		for(int i=1;i<arr.length;i++)
		{
			max=Math.max(Math.abs(arr[i]-arr[i-1]), max);
		}
		return max;
	}
	static void replace(long arr[], long n)
	{
		for(int i=0;i<arr.length;i++)
			if(arr[i]==-1)
				arr[i]=n;
	}
	static boolean isPerfectSquare(long l)
	{
		return Math.pow((long)Math.sqrt(l),2)==l;
	}
	
	
	void merge(int arr[], int l, int m, int r) 
    { 
        // Find sizes of two subarrays to be merged 
        int n1 = m - l + 1; 
        int n2 = r - m; 
  
        /* Create temp arrays */
        int L[] = new int [n1]; 
        int R[] = new int [n2]; 
  
        /*Copy data to temp arrays*/
        for (int i=0; i<n1; ++i) 
            L[i] = arr[l + i]; 
        for (int j=0; j<n2; ++j) 
            R[j] = arr[m + 1+ j]; 
  
  
        /* Merge the temp arrays */
  
        // Initial indexes of first and second subarrays 
        int i = 0, j = 0; 
  
        // Initial index of merged subarry array 
        int k = l; 
        while (i < n1 && j < n2) 
        { 
            if (L[i] <= R[j]) 
            { 
                arr[k] = L[i]; 
                i++; 
            } 
            else
            { 
                arr[k] = R[j]; 
                j++; 
            } 
            k++; 
        } 
  
        /* Copy remaining elements of L[] if any */
        while (i < n1) 
        { 
            arr[k] = L[i]; 
            i++; 
            k++; 
        } 
  
        /* Copy remaining elements of R[] if any */
        while (j < n2) 
        { 
            arr[k] = R[j]; 
            j++; 
            k++; 
        } 
    } 
  
    // Main function that sorts arr[l..r] using 
    // merge() 
    void sort(int arr[], int l, int r) 
    { 
        if (l < r) 
        { 
            // Find the middle point 
            int m = (l+r)/2; 
  
            // Sort first and second halves 
            sort(arr, l, m); 
            sort(arr , m+1, r); 
  
            // Merge the sorted halves 
            merge(arr, l, m, r); 
        } 
    } 
    static class Pair implements Comparable<Pair>{
        int a;
        int b;
        Pair(int a,int b){
            this.a=a;
 
            this.b=b;
        }   
        public int compareTo(Pair p){
            if(a>p.a)
                return 1;
            if(a==p.a)
                return (b-p.b);
            return -1;
        }
    }
	static class Reader 
    { 
        final private int BUFFER_SIZE = 1 << 16; 
        private DataInputStream din; 
        private byte[] buffer; 
        private int bufferPointer, bytesRead; 
  
        public Reader() 
        { 
            din = new DataInputStream(System.in); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public Reader(String file_name) throws IOException 
        { 
            din = new DataInputStream(new FileInputStream(file_name)); 
            buffer = new byte[BUFFER_SIZE]; 
            bufferPointer = bytesRead = 0; 
        } 
  
        public String readLine() throws IOException 
        { 
            byte[] buf = new byte[64]; // line length 
            int cnt = 0, c; 
            while ((c = read()) != -1) 
            { 
                if (c == '\n') 
                    break; 
                buf[cnt++] = (byte) c; 
            } 
            return new String(buf, 0, cnt); 
        } 
  
        public int nextInt() throws IOException 
        { 
            int ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do
            { 
                ret = ret * 10 + c - '0'; 
            }  while ((c = read()) >= '0' && c <= '9'); 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public long nextLong() throws IOException 
        { 
            long ret = 0; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        public double nextDouble() throws IOException 
        { 
            double ret = 0, div = 1; 
            byte c = read(); 
            while (c <= ' ') 
                c = read(); 
            boolean neg = (c == '-'); 
            if (neg) 
                c = read(); 
  
            do { 
                ret = ret * 10 + c - '0'; 
            } 
            while ((c = read()) >= '0' && c <= '9'); 
  
            if (c == '.') 
            { 
                while ((c = read()) >= '0' && c <= '9') 
                { 
                    ret += (c - '0') / (div *= 10); 
                } 
            } 
  
            if (neg) 
                return -ret; 
            return ret; 
        } 
  
        private void fillBuffer() throws IOException 
        { 
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
            if (bytesRead == -1) 
                buffer[0] = -1; 
        } 
  
        private byte read() throws IOException 
        { 
            if (bufferPointer == bytesRead) 
                fillBuffer(); 
            return buffer[bufferPointer++]; 
        } 
  
        public void close() throws IOException 
        { 
            if (din == null) 
                return; 
            din.close(); 
        } 
    } 
}