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.*;
import java.math.*;
import java.util.*;
import javax.print.attribute.SetOfIntegerSyntax;
 
public class Solution{
    private static InputStream stream;
    private static byte[] buf = new byte[1024];
    private static int curChar;
    private static int numChars;
    private static SpaceCharFilter filter;
    private static PrintWriter pw;
    private static long count = 0,mod=100000,max=0;
    private static TreeSet<Integer>ts[]=new TreeSet[200000];
    private static ArrayList<Integer>[] adj;
    private static boolean visited[];
    
    public static void main(String args[]) throws Exception {
        InputReader(System.in);
        pw = new PrintWriter(System.out); 
        new Thread(null ,new Runnable(){
           public void run(){
               try{
                   soln();
                   pw.close();
               } catch(Exception e){
                   e.printStackTrace();
               }
           }
       },"1",1<<26).start();
    }
    //----------------------------------------My Code------------------------------------------------//
    private static ArrayList<Integer> prime;

    private static void sieve(int n) {
	    	boolean visited[] = new boolean[n];
	    	visited[1] =true;
	    	for(int i=2;i<n;i++) {
	    		if(!visited[i]) {
	    			prime.add(i);
	    			for(int j = i+i;j<n;j+=i) {
	    				visited[j] = true;
	    			}
	    		}
	    	}
    }
    private static void soln(){
    		int q = nextInt();
    		while(q --> 0) {
    			int n = nextInt();
    			int[] arr = nextIntArray(n);
    			if(n==1) {
    				pw.println("YES");
    				continue;
    			}
    			int start_idx = -1;
    			for(int i=0;i<n;i++) {
    				if(arr[i]==1) {
    					start_idx = i;
//    					pw.println(start_idx);
    				}
    			}
    			int end_idx = (start_idx + 1)%n;
    			boolean ans = true;
    			for(int i=1;i<n;i++) {
    				if(arr[(end_idx+i)%n]>arr[(end_idx+i - 1)%n]) {
//    					pw.println("i: " +arr[(start_idx+i)%n] +" " + arr[(start_idx+i - 1)%n]);
    					ans = false;
    					break;
    				}
    			}
    			if(ans) {
    				pw.println("YES");
    				continue;
    			}
    			ans = true;
    			for(int i=1;i<n;i++) {
    				if(arr[(start_idx+i)%n]<arr[(start_idx+i-1)%n]) {
    					ans = false;
    					break;
    				}
    			}
    			if(ans) {
    				pw.println("YES");
    				continue;
    			}
    			pw.println("NO");
    		}
    }
    public static int bfs(int root, int key) {
    	boolean visited[] = new boolean[adj.length];
    	Queue<Integer> qu = new LinkedList<Integer>();
    	qu.add(root);
    	visited[root] = true;
    	int level = 0, increamenter = 1;//adj[root].size();
    	while(!qu.isEmpty()) {
    		int current = qu.poll();
    		if(current==key) return level;
    		increamenter--;
    		for(int x : adj[current]) {
    			if(!visited[x]) {
    				qu.add(x);
    				visited[x] = true;
    				if(x==key) return level+1;
    			}
    		}
    		if(increamenter==0) {
    			level++;
    			increamenter = qu.size();
    		}
    		//if(visited[key]) return level;
    	}
    	return 0;
    }
	//----------------------------------------THE END----------------------------------------------------------//            
	 
    static class Pair implements Comparable<Pair>{
 
       int idx,val;
       
        Pair(int idx,int val){
            this.idx=idx;
            this.val = val;
        }
        @Override
        public int compareTo(Pair o) {
           return Integer.compare(this.val, o.val);
            
        }
        //@Override
        public boolean equals(Pair o) {
        	return (this.idx==o.idx && this.val==o.val);
        }
        
        public int hashCode() {
        	return (Integer.hashCode(idx) + Integer.hashCode(val))%Integer.MAX_VALUE;
        }
    }
 
    public static long gcd(long x, long y) {
        if (x % y == 0)
            return y;
        else
            return gcd(y, x % y);
    }
    
    private static int BinarySearch(int a[], int low, int high, int target) {
        if (low > high)
            return -1;
        int mid = low + (high - low) / 2;
        if (a[mid] == target)
            return mid;
        if (a[mid] > target)
            high = mid - 1;
        if (a[mid] < target)
            low = mid + 1;
        return BinarySearch(a, low, high, target);
    }
    
    public static String reverseString(String s) {
        StringBuilder sb = new StringBuilder(s);
        sb.reverse();
        return (sb.toString());
    }
 
    
    
    public static long pow(long n, long p, long m) {
        long result = 1;
        if (p == 0)
            return 1;
        if (p == 1)
            return n;
        while (p != 0) {
            if (p % 2 == 1)
                result *= n;
            if (result >= m)
                result %= m;
            p >>= 1;
            n *= n;
            if (n >= m)
                n %= m;
        }
        return result;
    }
 
    public static long pow(long n, long p) {
        long result = 1;
        if (p == 0)
            return 1;
        if (p == 1)
            return n;
        while (p != 0) {
            if (p % 2 == 1)
                result *= n;
            p >>= 1;
            n *= n;
        }
        return result;
 
    }
 
     public static int[] radixSort(int[] f) {
        int[] to = new int[f.length];
        {
            int[] b = new int[65537];
            for (int i = 0; i < f.length; i++)
                b[1 + (f[i] & 0xffff)]++;
            for (int i = 1; i <= 65536; i++)
                b[i] += b[i - 1];
            for (int i = 0; i < f.length; i++)
                to[b[f[i] & 0xffff]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        {
            int[] b = new int[65537];
            for (int i = 0; i < f.length; i++)
                b[1 + (f[i] >>> 16)]++;
            for (int i = 1; i <= 65536; i++)
                b[i] += b[i - 1];
            for (int i = 0; i < f.length; i++)
                to[b[f[i] >>> 16]++] = f[i];
            int[] d = f;
            f = to;
            to = d;
        }
        return f;
    }
 
    public static int nextPowerOf2(final int a) {
        int b = 1;
        while (b < a) {
            b = b << 1;
        }
        return b;
    }
 
    public static boolean PointInTriangle(int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8) {
        int s = p2 * p5 - p1 * p6 + (p6 - p2) * p7 + (p1 - p5) * p8;
        int t = p1 * p4 - p2 * p3 + (p2 - p4) * p7 + (p3 - p1) * p8;
 
        if ((s < 0) != (t < 0))
            return false;
 
        int A = -p4 * p5 + p2 * (p5 - p3) + p1 * (p4 - p6) + p3 * p6;
        if (A < 0.0) {
            s = -s;
            t = -t;
            A = -A;
        }
        return s > 0 && t > 0 && (s + t) <= A;
    }
 
    public static float area(int x1, int y1, int x2, int y2, int x3, int y3) {
        return (float) Math.abs((x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0);
    }
 
    public static boolean isPrime(int n) {
        // Corner cases
        if (n <= 1)
            return false;
        if (n <= 3)
            return true;
 
        // This is checked so that we can skip 
    // middle five numbers in below loop
        if (n % 2 == 0 || n % 3 == 0)
            return false;
 
        for (int i = 5; i * i <= n; i = i + 6)
            if (n % i == 0 || n % (i + 2) == 0)
                return false;
 
        return true;
    }
 
    //merge Sort
 
    static long sort(int a[])
    {  int n=a.length;
        int b[]=new int[n];    
        return mergeSort(a,b,0,n-1);}
    static long mergeSort(int a[],int b[],long left,long right)
    { long c=0;if(left<right)
     {   long mid=left+(right-left)/2;
         c= mergeSort(a,b,left,mid);
         c+=mergeSort(a,b,mid+1,right);
         c+=merge(a,b,left,mid+1,right); }    
        return c;     }
    static long merge(int a[],int  b[],long left,long mid,long right)
    {long c=0;int i=(int)left;int j=(int)mid; int k=(int)left;
    while(i<=(int)mid-1&&j<=(int)right)
    { if(a[i]>a[j]) {b[k++]=a[i++]; }
    else    { b[k++]=a[j++];c+=mid-i;}}
    while (i <= (int)mid - 1)   b[k++] = a[i++]; 
    while (j <= (int)right) b[k++] = a[j++];
    for (i=(int)left; i <= (int)right; i++) 
        a[i] = b[i];  return c;  }
 
    // To Get Input
// Some Buffer Methods
 
    public static void InputReader(InputStream stream1) {
        stream = stream1;
    }
 
    private static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }
 
    private static boolean isEndOfLine(int c) {
        return c == '\n' || c == '\r' || c == -1;
    }
 
    private static 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++];
    }
 
    private static 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;
    }
 
    private static 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;
    }
 
    private static String nextToken() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }
 
    private static 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();
    }
 
    private static int[] nextIntArray(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }
        return arr;
    }
 
    private static int[][] next2dArray(int n, int m) {
        int[][] arr = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                arr[i][j] = nextInt();
            }
        }
        return arr;
    }
 
    private static long[] nextLongArray(int n) {
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextLong();
        }
        return arr;
    }
 
    private static void pArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            pw.print(arr[i] + " ");
        }
        pw.println();
        return;
    }
 
    private static void pArray(long[] arr) {
        for (int i = 0; i < arr.length; i++) {
            pw.print(arr[i] + " ");
        }
        pw.println();
        return;
    }
 
    private static void pArray(boolean[] arr) {
        for (int i = 0; i < arr.length; i++) {
            pw.print(arr[i] + " ");
        }
        pw.println();
        return;
    }
 
    private static boolean isSpaceChar(int c) {
        if (filter != null)
            return filter.isSpaceChar(c);
        return isWhitespace(c);
    }
 
    private interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}