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

public class Main {

    private static int MOD = 1000000007;

    public static void main(String[] args) throws Exception {
//        InputStream inS = System.in;
//        InputReader sc = new InputReader(inS);
        Helpers helpers = new Helpers();
        PrintStream out = System.out;
        Scanner sc = new Scanner(System.in);

        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
//
            int[] arr = new int[n];
//
            for (int i = 0; i < n; i++) {
                arr[i] = sc.nextInt();
            }

//        Leetcode question = new Leetcode();


            if (checkClockwise(arr) || checkAnticlockwise(arr)) {
                out.println("YES");
            } else {
                out.println("NO");
            }
        }

        out.close();
    }

    private static  boolean checkClockwise(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (!(arr[i] > arr[i-1] || arr[i] == 1)) {
                return false;
            }
        }

        return true;
    }

    private static boolean checkAnticlockwise(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            if (!(arr[i] < arr[i-1] || arr[i] == arr.length)) {
                return false;
            }
        }

        return true;
    }

    private static class Leetcode {
        public int maximalRectangle(char[][] matrix) {
            if (matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }

            Cell[][] cells = new Cell[matrix.length][matrix[0].length];
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    cells[i][j] = new Cell();
                }
            }
            setRows(matrix, cells);
            setColumns(matrix, cells);

            // calculate areas
            setAreas(cells);

            // validate areas
            validateAreas(cells, matrix);


            int max = 0;
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    if (matrix[i][j] == '1') {
                        max = Math.max(max, cells[i][j].area);
                    }
                }
            }

            return max;
        }

        private void setAreas(Cell[][] cells) {
            for (int i = 0; i < cells.length; i++) {
                for (int j = 0; j < cells[0].length; j++) {
                    cells[i][j].area = cells[i][j].down * cells[i][j].right;
                }
            }
        }

        private void validateAreas(Cell[][] cells, char[][] matrix) {
            // reverse thru the matrix and validate diagonal cells
            for (int i = cells.length-1; i > 0; i--) {
                for (int j = cells[0].length-1; j > 0; j--) {
                    if (matrix[i][j] == '1' && matrix[i-1][j-1] == '1') {
                        cells[i-1][j-1].area = Math.min(cells[i][j].down + 1, cells[i-1][j-1].down) * Math.min(cells[i][j].right + 1, cells[i-1][j-1].right);
                    }
                }
            }
        }

        private void setRows(char[][] arr, Cell[][] cells) {
            for (int i = 0; i < arr.length; i++) {
                setRow(arr, i, cells);
            }
        }

        private void setColumns(char[][] arr, Cell[][] cells) {
            for (int i = 0; i < arr[0].length; i++) {
                setColumn(arr, i, cells);
            }
        }

        private void setRow(char[][] arr, int index, Cell[][] cells) {
            Stack<Integer> monoIncN = new Stack<>();

            for (int i = 0; i < cells[0].length; i++) {
                cells[index][i].right = cells[0].length - i;
            }

            for (int i = 0; i < arr[0].length; i++) {

                while (!monoIncN.isEmpty() && arr[index][monoIncN.peek()] > arr[index][i]) {
                    int temp = monoIncN.pop();
                    cells[index][temp].right = i - temp;
                }

                monoIncN.push(i);
            }
        }

        private void setColumn(char[][] arr, int index, Cell[][] cells) {
            Stack<Integer> monoIncN = new Stack<>();

            for (int i = 0; i < cells.length; i++) {
                cells[i][index].down = cells.length - i;
            }

            for (int i = 0; i < arr.length; i++) {
                while (!monoIncN.isEmpty() && arr[monoIncN.peek()][index] > arr[i][index]) {
                    int temp = monoIncN.pop();
                    cells[temp][index].down = i - temp;
                }

                monoIncN.push(i);
            }
        }

        private static class Cell {
            int down, right, area;
        }
    }

    static int lis(int arr[], int n) {
        int result = 0;
        int[] lis = new int[n];

        for (int i = 0; i < n; i++) {
            lis[i] = 1;
        }

        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[i] > arr[j] && lis[i] < lis[j] + 1) {
                    lis[i] = lis[j] + 1;
                }
            }
        }

        for (int i = 0; i < n; i++) {
            if (result < lis[i]) {
                result = lis[i];
            }
        }

        return result;
    }


    public static void takeIntInput(Scanner sc, long[] arr) {
        for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextLong();
        }
    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }

    static class Helpers {
        public  boolean less(Comparable a, Comparable b) {
            return a.compareTo(b) < 0;
        }

        public  boolean less(Comparator c, Object a, Object b) {
            return c.compare(a, b) < 0;
        }

        public  void exch(Object[] a, int i, int j) {
            Object swap = a[i];
            a[i] = a[j];
            a[j] = swap;
        }

        public  void main(String[] args) {
            Scanner sc = new Scanner(System.in);

            int n = sc.nextInt();
            while (n > 0) {
                System.out.print('(');
                n--;
            }
        }
        public  boolean isSorted(Comparable[] a) {
            return isSorted(a, 0, a.length-1);
        }

        /**
         *
         * @param a
         * @param start lie b/w 0 and length - 1
         * @param end lie b/w 0 and length - 1
         * @return if sorted b/w start and end indices
         */
        public  boolean isSorted(Comparable[] a, int start, int end) {
            for (int i = start ; i < end ; i++) {
                if (!less(a[i], a[i+1])) {
                    return false;
                }
            }

            return true;
        }

        public  boolean isSorted(Object[] a, int start, int end, Comparator c) {
            for (int i = start ; i < end ; i++) {
                if (!less(c, a[i], a[i+1])) {
                    return false;
                }
            }

            return true;
        }

        public  void copy(Object[] from, Object[] to, int lo, int hi) {
            for (int i = lo; i <= hi; i++) {
                to[i] = from[i];
            }
        }

        public  void display(Object[] a, int from, int to) {
            for (int i = from; i <= to; i++) {
                System.out.print(a[i] +  " ");
            }

            System.out.println();
        }

        public  void display(int[] a, int from, int to) {
            for (int i = from; i <= to; i++) {
                System.out.print(a[i] +  " ");
            }

            System.out.println();
        }

        public String display(List<Integer> arr) {
            StringBuilder sb = new StringBuilder();
            for (Integer i : arr) {
                sb.append(i);
                sb.append(" ");
            }
            return sb.toString();
        }

        public  void display(char[] a, int from, int to) {
            for (int i = from; i <= to; i++) {
                System.out.print(a[i] +  " ");
            }

            System.out.println();
        }

        public  void takeIntInput(Scanner sc, Integer[] arr) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextInt();
            }
        }

        public  void takeIntInput(Main.InputReader sc, int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextInt();
            }
        }

        public  int getMax(int[] arr) {
            int max = Integer.MIN_VALUE;

            for (int i = 0; i < arr.length; i++) {
                max = Math.max(max, arr[i]);
            }

            return max;
        }

        public  void takeIntInput(Scanner sc, int[] arr) {
            for (int i = 0; i < arr.length; i++) {
                arr[i] = sc.nextInt();
            }
        }

        public  int[] toArray(ArrayList<Integer> al) {
            int[] ret = new int[al.size()];
            for (int i = 0 ; i < al.size() ; i++) {
                ret[i] = al.get(i);
            }

            return ret;
        }

        public  boolean isLeapYear(int year) {
            return year % 4 == 0 && (year % 100 != 0 || year % 400 == 0);
        }

        public long getProduct(int[] arr) {
            long product = 1;
            for (int i = 0; i < arr.length; i++) {
                product *= arr[i];
            }

            return product;
        }
    }

}
