There are n students standing in a circle in some order. The index of the i-th student is p_i. It is guaranteed that all indices of students are distinct integers from 1 to n (i. e. they form a permutation).

Students want to start a round dance. A clockwise round dance can be started if the student 2 comes right after the student 1 in clockwise order (there are no students between them), the student 3 comes right after the student 2 in clockwise order, and so on, and the student n comes right after the student n - 1 in clockwise order. A counterclockwise round dance is almost the same thing — the only difference is that the student i should be right after the student i - 1 in counterclockwise order (this condition should be met for every i from 2 to n). 

For example, if the indices of students listed in clockwise order are [2, 3, 4, 5, 1], then they can start a clockwise round dance. If the students have indices [3, 2, 1, 4] in clockwise order, then they can start a counterclockwise round dance.

Your task is to determine whether it is possible to start a round dance. Note that the students cannot change their positions before starting the dance; they cannot swap or leave the circle, and no other student can enter the circle. 

You have to answer q independent queries.

Input

The first line of the input contains one integer q (1 ≤ q ≤ 200) — the number of queries. Then q queries follow.

The first line of the query contains one integer n (1 ≤ n ≤ 200) — the number of students.

The second line of the query contains a permutation of indices p_1, p_2, ..., p_n (1 ≤ p_i ≤ n), where p_i is the index of the i-th student (in clockwise order). It is guaranteed that all p_i are distinct integers from 1 to n (i. e. they form a permutation).

Output

For each query, print the answer on it. If a round dance can be started with the given order of students, print "YES". Otherwise print "NO".

Example

Input


5
4
1 2 3 4
3
1 3 2
5
1 2 3 5 4
1
1
5
3 2 1 5 4


Output


YES
YES
NO
YES
YES
    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 Main6{
     
    	static class Pair
    		{ 
    			int x;
    			int y;
    			public Pair(int x,int y) 
    			{	 
    				this.x= x; 
    				this.y= y;
    			}	 
				
			@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
    		{
    			String x;
    			int y;
    			int z;
    			
    		}
    		static class Compare
    		{ 
    			/*static void compare(Pair arr[], int n) 
    			{ 
    				// Comparator to sort the pair according to second element 
    				Arrays.sort(arr, new Comparator<Pair>() { 
    					@Override public int compare(Pair p1, Pair p2) 
    					{ 
    						if(p1.start>p2.start)
    						{
    							return 1;
    						}
    						else if(p1.start==p2.start)
    						{
    							return 0;
    						}
    						else
    						{
    							return -1;
    						}
    					} 
    				}); 
    			}
    			*/
    		}
    		
    		
    		public static long pow(long a, long b)
    		{
    			long result=1;
    			while(b>0)
    			{
    				if (b % 2 != 0)
    				{
    					result=(result*a)%998244353;
    					b--;
    				} 
    				a=(a*a)%998244353;
    				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 int gcd(int a, int 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 long sum(int h)
    				{
    					return (h*(h+1)/2);
    				}
    				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;
    				
    				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;
    				
    				
    				
    				
    				
    				
    				
    				
    				
    			//	static int[] a;			  
    				
    				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 public void main(String args[])throws IOException
    				{
    		//		    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
    			/*		boolean[] prime=new boolean[1101];
    					for(int i=2;i*i<=1100;i++)
    					{
    						if(prime[i]==false)
    						{
    							for(int j=2*i;j<=1100;j+=i)
    							{
    								prime[j]=true;
    							}
    						}
    					}*/
						int q=i();
						while(q-->0)
						{
							int n=i();
							int[] a=new int[2*n];
							int flag=0;
							for(int i=0;i<n;i++)
							{
								a[i]=i();
							}
							if(n==1)
								pln("YES");
							else{
							for(int i=n;i<2*n;i++)
							{
								a[i]=a[i-n];
							}
							int count=0;
						//	pln(Arrays.toString(a));
							for(int i=0;i<2*n;i++)
							{
								count=0;
								for(int j=i;j<2*n-1;j++)
								{
									if(a[j]+1==a[j+1])
										count++;
									else
									{
										break;
									}
								}
								if(count==n-1)
								{
									flag=1;
									break;
								}
							}
							if(flag==1)
								pln("YES");
							else
							{
								count=0;
								for(int i=0;i<2*n;i++)
								{
									count=0;
									for(int j=i;j<2*n-1;j++)
									{		
										if(a[j]==a[j+1]+1)
										count++;
										else
										{
											break;
										}
									}
									if(count==n-1)
									{
										flag=1;
										break;
									}
								}
								if(flag==1)
									pln("YES");
								else
									pln("NO");
							}
							}
						}
					}
					
    				
    	
    					
    				
    				
    				
    				
    				
    				
    				
    				
    				
    				
    				
    				
    				
    				/**/
    				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;
    				}
    			 
    				} 