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 sys
import math
# stdin_fileno = sys.stdin
 
# Input processing funcs: https://www.journaldev.com/23625/python-trim-string-rstrip-lstrip-strip
# https://stackoverflow.com/questions/1450393/how-do-you-read-from-stdin?rq=1#:~:text=stdin%20is%20a%20file%2Dlike,use%20raw_input%20in%20Python%202.
# https://www.geeksforgeeks.org/python-input-methods-competitive-programming/
#https://stackoverflow.com/questions/22623528/sys-stdin-readline-and-input-which-one-is-faster-when-reading-lines-of-inpu#:~:text=stdin.,-readline()%20and&text=input%2C%20as%20sys.-,stdin.,input()%20when%20reading%20integers.
# last link tells that stdin is much faster than input. stdout seems to be faster than print (geeksforgeeks link)


# you can use sys.stdin like fin
# sys.stdin = open('in','r') # comment this line when you submit

# Remember, this is available: [int(item) for item in sys.stdin.readline().rstrip().split(" ")]
# rstrip, lstrip, strip are useful functions, as well as split.



# sys.stdout.write(str(n)) # stdout requires everything to be a string when printed, and doesn't add \n. just use it for final output because print is obv easier to type though stdout is faster


t = int(sys.stdin.readline().rstrip())
for k in range (0, t):
    n = int(sys.stdin.readline().rstrip())
    x = sys.stdin.readline().rstrip().split (' ')
    a = True
    b = True
    c = int (x [ - 1])
    if n == 1:
        sys.stdout.write('YES\n')
    else:
        for h, i in enumerate (x):
            if int (i) != c + 1 and int (i) != 1:
                a = False
            if int (i) != c - 1 and int (i) != len (x):
                b = False
            c = int (i)
        if a or b:
            sys.stdout.write('YES\n')
        else:
            sys.stdout.write('NO\n')