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.util.*;

public class Main {
    private static PrintWriter out;
    private static Scanner in;
    private static BufferedReader br;
    private static StringTokenizer st = new StringTokenizer("");

    private int ni() throws IOException {
        //nextInt
        return Integer.parseInt(ns());
    }

    private String ns() throws IOException {
        //next
        while (!st.hasMoreElements()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    public static void main(String[] args) throws IOException {
        new Main().solve();
    }

    private void solve() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        Out out = new Out();
        int q = ni();
        for (int i = 0; i < q; i++) {
            int n = ni();
            int []a = new int[n];
            for (int j = 0; j < n; j++) {
                a[j] = ni();
            }
            int was1 = 0;
            int was2 = 0;
            for (int j = 1; j < n; j++) {
                if(a[j] - a[j-1] != 1)was1++;
            }
            for (int j = 1; j < n; j++) {
                if(a[j-1] - a[j] != 1)was2++;
            }
            if(was1 > 1 && was2 > 1) System.out.println("NO");
            else System.out.println("YES");
        }

    }
    private String rev(String s){
        return new StringBuffer(s).reverse().toString();
    }
     private void ftvsst(){
        int n = 100000;
        int testCnt = 100000;
        int []a = new int[n];
        Random rnd = new Random();
        for (int i = 0; i < n; i++) {
            a[i] = rnd.nextInt();
        }
        SegmentTree st = new SegmentTree(a);
        FenwickTree ft = new FenwickTree(a);
        int ftavgSETTIME = 0;
        int stavgSETTIME = 0;
        int ftavgGETTIME = 0;
        int stavgGETTIME = 0;
        for (int i = 0; i < testCnt; i++) {
            st.actCnt = 0;
            ft.actCnt = 0;
            int left = rnd.nextInt();
            int right = rnd.nextInt();
            if(left < 0)left = -left;
            if(right < 0)right = -right;
            left%=n;
            right%=n;
            if(ft.sum(Math.min(left,right),Math.max(left,right)) != st.get(1,0,n-1,Math.min(left,right),Math.max(left,right))){
                System.out.println("SOMETHING WENT WRONG");
                return;
            }
            ftavgGETTIME+=ft.actCnt;
            stavgGETTIME+=st.actCnt;
        }
        stavgGETTIME/=testCnt;
        ftavgGETTIME/=testCnt;
        for (int i = 0; i < testCnt; i++) {
            st.actCnt = 0;
            ft.actCnt = 0;
            int pos = rnd.nextInt();
            if(pos < 0)pos = -pos;
            pos%=n;
            int val = rnd.nextInt()%1000;
            ft.inc(pos,val);
            st.set(1,0,n-1,pos,val);
            ftavgSETTIME+=ft.actCnt;
            stavgSETTIME+=st.actCnt;
        }
        stavgSETTIME/=testCnt;
        ftavgSETTIME/=testCnt;
        System.out.println("FT AVG SET TIME : " + ftavgSETTIME);
        System.out.println("ST AVG SET TIME : " + stavgSETTIME);
        System.out.println("FT AVG GET TIME : " + ftavgGETTIME);
        System.out.println("ST AVG GET TIME : " + stavgGETTIME);
    }
    long toLong(String a) {
        long cnt = 1;
        for (int i = 1; i < a.length(); i++) {
            cnt *= 2;
            cnt += Integer.parseInt(a.charAt(i) + "");
        }
        return cnt;
    }
    String toBinary(long a) {
        return Long.toBinaryString(a);
    }
}

class SegmentTree {
    private long[] t;
    private int[] a;
    public int actCnt;
    SegmentTree(int[] a) {
        this.a = a;
        t = new long[4 * a.length];
        build(1, 0, a.length - 1);
    }

    private void build(int v, int tl, int tr) {
        if (tl == tr) t[v] = a[tl];
        else {
            int tm = (tl + tr) / 2;
            build(v * 2, tl, tm);
            build(v * 2 + 1, tm + 1, tr);
            t[v] = t[v * 2] + t[v * 2 + 1];
        }
    }

    void set(int v, int tl, int tr, int pos, int val) {
        actCnt++;
        if (tl == tr) t[v] = val;
        else {
            int tm = (tl + tr) / 2;
            if (pos <= tm) set(v * 2, tl, tm, pos, val);
            else set(v * 2 + 1, tm + 1, tr, pos, val);
            t[v] = t[v * 2] + t[v * 2 + 1];
        }
    }

    long get(int v, int tl, int tr, int l, int r) {
        actCnt++;
        if (tl > r || tr < l) return 0;
        if (l <= tl && r >= tr) return t[v];
        int tm = (tl + tr) / 2;
        return get(v * 2, tl, tm, l, r) + get(v * 2 + 1, tm + 1, tr, l, r);
    }
}

class FenwickTree {
    private int n;
    private int[] a;
    private long t[];
    public int actCnt;
    FenwickTree(int[] a) {
        this.a = a;
        n = a.length;
        t = new long[n];
        for (int i = 0; i < n; i++) {
            inc(i, a[i]);
        }
    }

    void inc(int i, int delta) {
        actCnt++;
        //if i-th element is q , i-th element becomes q+delta
        for (; i < n; i = (i | (i + 1))) {
            actCnt++;
            t[i] += delta;
        }
    }
    long sum(int r) {
        long res = 0;
        actCnt++;
        for (; r >= 0; r = (r & (r + 1)) - 1) {
            actCnt++;
            res += t[r];
        }
        return res;
    }

    long sum(int l, int r) {
        return sum(r) - sum(l - 1);
    }
}

class DSU {
    private int[] p;

    DSU(int n) {
        p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = i;
        }
    }

    void make_set(int i) {
        p[i] = i;
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) p[a] = b;
    }

    private int find_set(int a) {
        if (p[a] == a) return a;
        return p[a] = find_set(p[a]);
    }
}

class Out {
    private PrintWriter out;

    Out() {
        out = new PrintWriter(System.out);
    }

    void print(int a) {
        out.print(a);
    }

    void print(long a) {
        out.print(a);
    }

    void print(String a) {
        out.print(a);
    }

    void println(int a) {
        out.println(a);
    }

    void println(long a) {
        out.println(a);
    }

    void println(String a) {
        out.println(a);
    }

}