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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.Writer;
import java.util.Arrays;
import java.util.InputMismatchException;
import java.util.*;
import java.io.*;
import java.math.*;
public class Main7
{
	static class Pair
	{ 
		int x;
		int y;
		int z;
		int p;
		public Pair(int x, int y,int z, int p) 
		{     
			this.x=x;
			this.y=y;
			this.z=z;
			this.p=p;
		}
		    
   /* @Override
            public int hashCode() 
            { 
                final int temp = 14; 
                int ans = 1; 
                ans =x*31+y*13; 
                return ans; 
            } 
      
            // Equal objects must produce the same 
            // hash code as long as they are equal 
        @Override
        public boolean equals(Object o) 
        { 
            if (this == o) { 
                return true; 
            } 
            if (o == null) { 
                return false; 
            } 
            if (this.getClass() != o.getClass()) { 
                return false; 
            } 
            Pair other = (Pair)o; 
            if (this.x != other.x || this.y!=other.y) { 
                return false; 
            } 
            return true; 
        }*/
	} 
	static class Pair1
	{
		int x;
		int y;
		long z;
		Pair1(int x, int y, long z)
		{
			this.x=x;
			this.y=y;
			this.z=z;
		}
	}
    public static long pow(long a, long b)
    {
        long result=1;
        while(b>0)
        {
            if (b % 2 != 0)
            {
                result=(result*a);
                b--;
            } 
            a=(a*a);
            b /= 2;
        }   
        return result;
    }
    public static long fact(long num)
    {
		long value=1;
		int i=0;
		for(i=2;i<num;i++)
		{
			value=((value%mod)*i%mod)%mod;
		}
		return value;
	}
	public static long gcd(long a, long b)
	{
		if (a == 0)
			return b;
		return gcd(b%a, a);
	}	
	public static long lcm(long a,long b)
	{
		return a * (b / gcd(a, b));
	}
/*   public static void dfs(int parent,boolean[] visited,int[] dp)
	{
		ArrayList<Integer> arr=new ArrayList<Integer>();
		arr=graph.get(parent);
		visited[parent]=true;
		for(int i=0;i<arr.size();i++)
		{
			int num=(int)arr.get(i);
			if(visited[num]==false)
			{
				dfs(num,visited,dp);
			}
			dp[parent]=Math.max(dp[num]+1,dp[parent]);
		}
	}
//  static int flag1=0;
	static int[] dis;*/
	static int mod=1000000007;
	static ArrayList<ArrayList<Integer>> graph;
	static ArrayList<ArrayList<Integer>> g;
/*    public static void bfs(int num,int size)
	{
		boolean[] visited=new boolean[size+1];
		Queue<Integer> q=new LinkedList<>();
		q.add(num);
		ans[num]=1;
		visited[num]=true;
		while(!q.isEmpty())
		{
			int x=q.poll();
			ArrayList<Integer> al=graph.get(x);
			for(int i=0;i<al.size();i++)
			{
				int y=al.get(i);    
				if(visited[y]==false)
				{
					q.add(y);
					ans[y]=ans[x]+1;
					visited[y]=true;
				}
			}
		}
	}
	static int[] ans;*/
	public static int[] sort(int[] a)
	{
		int n=a.length;
		ArrayList<Integer> ar=new ArrayList<>();
		for(int i=0;i<a.length;i++)
		{
			ar.add(a[i]);
		}
		Collections.sort(ar);
		for(int i=0;i<n;i++)
		{
			a[i]=ar.get(i);
		}
		return a;
	}
	static int find(int num)
	{
		if(parent[num]!=num)
		{
			parent[num]=find(parent[num]);
		}
		return parent[num];
	} 
	static void union(int x , int y ) 
	{ 
		int xroot = find(x); 
		int yroot = find(y); 
	  
		if (rank[xroot] < rank[yroot]) 
		{
			parent[xroot] = yroot; 
			size[yroot]+=size[xroot];
			size[xroot]=size[yroot];
		}
		else if (rank[yroot] < rank[xroot]) 
		{
			parent[yroot] = xroot; 
			size[xroot]+=size[yroot];
			size[yroot]=size[xroot];
		}
		else
		{ 
			parent[xroot] = yroot; 
			rank[yroot]++; 
			size[yroot]+=size[xroot];
			size[xroot]=size[yroot];
		} 
	} 
	static int[] parent;
	static int[] rank;
	static int[] size;
	static public void main(String args[])throws IOException
	{
		int tt=i();
		StringBuilder sb=new StringBuilder();
		while(tt-->0)
		{
			int n=i();
			long[] a=new long[n];
			ArrayList<Long> ar3=new ArrayList<>();
			ArrayList<Long> ar=new ArrayList<>();
			long last=0;
			for(int i=0;i<n;i++)
			{
				a[i]=i();
				ar3.add(a[i]);
				if(i==0)
				{
					ar.add(a[i]);
					last=a[i];
				}
				else
				{
					if(last==-1 && a[i]==-1)
					{
						
					}
					else
					{
						ar.add(a[i]);
						last=a[i];
					}
				}
			}
			long max=0;
			for(int i=0;i<n-1;i++)
			{
				if(a[i]!=-1 && a[i+1]!=-1)
				{
					max=Math.max(max,Math.abs(a[i+1]-a[i]));
				}
			}
			long num=0;
			long count=0;
			if(ar.size()==1)
			{
				sb.append("0 0\n");
			}
			else
			{
				ArrayList<Long> ar2=new ArrayList<>();
				for(int i=0;i<ar.size();i++)
				{
					if(ar.get(i)==-1)
					{
						if(i-1>=0 && i+1<ar.size())
						{
							num=num+ar.get(i-1)+ar.get(i+1);
							ar2.add(ar.get(i-1));
							ar2.add(ar.get(i+1));
							count+=2;
						}
						else if(i-1>=0)
						{
							num=num+ar.get(i-1);
							ar2.add(ar.get(i-1));
							count++;
						}
						else if(i+1<ar.size())
						{
							num=num+ar.get(i+1);
							ar2.add(ar.get(i+1));
							count++;
						}
					}
				}
				Collections.sort(ar2);
				if(ar2.size()%2==1)
				{
					long mid=ar2.get((ar2.size()/2));
					long[] b=new long[ar.size()];
					for(int i=0;i<ar.size();i++)
					{
						b[i]=ar.get(i);
					}
					for(int i=0;i<ar.size();i++)
					{
						if(b[i]==-1)
						{
							b[i]=mid;
						}
					}
					long maxx=0;
					for(int i=0;i<ar.size()-1;i++)
					{
						maxx=Math.max(maxx,Math.abs(b[i]-b[i+1]));
					}
					for(int i=0;i<ar.size();i++)
					{
						b[i]=ar.get(i);
					}
					for(int i=0;i<ar.size();i++)
					{
						if(b[i]==-1)
						{
							b[i]=mid-1;
						}
					}
					long maxxx=0;
					for(int i=0;i<ar.size()-1;i++)
					{
						maxxx=Math.max(maxxx,Math.abs(b[i]-b[i+1]));
					}
					if(max>=maxx)
					{
						sb.append(max+" "+mid+"\n");
					}
					else if(max>=maxxx)
					{
						sb.append(max+" "+(mid+1)+"\n");
					}
					else if(max<maxx && max<maxxx)
					{
						if(maxx<maxxx)
						{
							sb.append(maxx+" "+mid+"\n");
						}
						else
						{
							sb.append(maxxx+" "+(mid+1)+"\n");
						}
					}
				}
				else
				{
					long mid=(ar2.get(ar2.size()/2)+ar2.get(ar2.size()/2-1))/2;
					long[] b=new long[ar.size()];
					for(int i=0;i<ar.size();i++)
					{
						b[i]=ar.get(i);
					}
					for(int i=0;i<ar.size();i++)
					{
						if(b[i]==-1)
						{
							b[i]=mid;
						}
					}
					long maxx=0;
					for(int i=0;i<ar.size()-1;i++)
					{
						maxx=Math.max(maxx,Math.abs(b[i]-b[i+1]));
					}
					for(int i=0;i<ar.size();i++)
					{
						b[i]=ar.get(i);
					}
					for(int i=0;i<ar.size();i++)
					{
						if(b[i]==-1)
						{
							b[i]=mid+1;
						}
					}
					long maxxx=0;
					for(int i=0;i<ar.size()-1;i++)
					{
						maxxx=Math.max(maxxx,Math.abs(b[i]-b[i+1]));
					}
					if(max>=maxx)
					{
						sb.append(max+" "+mid+"\n");
					}
					else if(max>=maxxx)
					{
						sb.append(max+" "+(mid+1)+"\n");
					}
					else if(max<maxx && max<maxxx)
					{
						if(maxx<maxxx)
						{
							sb.append(maxx+" "+mid+"\n");
						}
						else
						{
							sb.append(maxxx+" "+(mid+1)+"\n");
						}
					}
				}
			/*	long ans=num/(count);
				//pln(ans+" "+count+" "+num);
				long[] b=new long[ar.size()];
				for(int i=0;i<ar.size();i++)
				{
					b[i]=ar.get(i);
				}
				for(int i=0;i<ar.size();i++)
				{
					if(b[i]==-1)
					{
						b[i]=ans;
					}
				}
				long maxx=0;
				for(int i=0;i<ar.size()-1;i++)
				{
					maxx=Math.max(maxx,Math.abs(b[i]-b[i+1]));
				}
				for(int i=0;i<ar.size();i++)
				{
					b[i]=ar.get(i);
				}
				for(int i=0;i<ar.size();i++)
				{
					if(b[i]==-1)
					{
						b[i]=ans+1;
					}
				}
				long maxxx=0;
				for(int i=0;i<ar.size()-1;i++)
				{
					maxxx=Math.max(maxxx,Math.abs(b[i]-b[i+1]));
				}*/
			}
		}
		System.out.print(sb.toString());
	} 
			/**/
	static InputReader in=new InputReader(System.in);
	static OutputWriter out=new OutputWriter(System.out);
	public static long l()
	{
		String s=in.String();
		return Long.parseLong(s);
	}
	public static void pln(String value)
	{
		System.out.println(value);
	}
	public static int i()
	{
		return in.Int();
	}
	public static String s()
	{
		return in.String();
	}
}
	class InputReader 
	{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
	 
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
	 
		public int read() {
			if (numChars== -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
	 
		public int Int() {
			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 String String() {
			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 boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	 
		public String next() {
			return String();
		}
	 
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
	 
	class OutputWriter {
		private final PrintWriter writer;
	 
		public OutputWriter(OutputStream outputStream) {
			writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
		}
	 
		public OutputWriter(Writer writer) {
			this.writer = new PrintWriter(writer);
		}
	 
		public void print(Object...objects) {
			for (int i = 0; i < objects.length; i++) {
				if (i != 0)
					writer.print(' ');
				writer.print(objects[i]);
			}
		}
	 
		public void printLine(Object...objects) {
			print(objects);
			writer.println();
		}
	 
		public void close() {
			writer.close();
		}
	 
		public void flush() {
			writer.flush();
		}
	 
		}
	 
		class IOUtils {
	 
		public static int[] readIntArray(InputReader in, int size) {
			int[] array = new int[size];
			for (int i = 0; i < size; i++)
				array[i] = in.Int();
			return array;
		}
	 
	} 

