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 \le q \le 200$) — the number of queries. Then $q$ queries follow.

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

The second line of the query contains a permutation of indices $p_1, p_2, \dots, p_n$ ($1 \le p_i \le 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
[{"code": "'''input\n5\n4\n1 2 3 4\n3\n1 3 2\n5\n1 2 3 5 4\n1\n1\n5\n3 2 1 5 4\n\n'''\nimport sys\nfrom collections import defaultdict as dd\nfrom itertools import  permutations as pp\nfrom itertools import combinations as cc\nfrom collections import Counter as ccd\nfrom random import randint as rd\nfrom bisect import bisect_left as bl\nfrom  heapq import heappush as hpush\nfrom heapq import heappop as hpop\nmod=10**9+7\n\ndef ri(flag=0):\n\tif flag==0:\n\t\treturn [int(i) for i in sys.stdin.readline().split()]\n\telse:\n\t\treturn int(sys.stdin.readline())\n\n\n\nfor _ in range(ri(1)):\n\tn = ri(1)\n\ta= ri()\n\tidx = a.index(1)\n\n\tcheck1 = 1\n\tcheck2 =1\n\tfor i in range(n):\n\t\tif a[(idx+i)%n] == i+1:\n\t\t\tpass\n\t\telse:\n\t\t\tcheck1=0\n\ta=a[::-1]\n\tidx = a.index(1)\n\tfor i in range(n):\n\t\tif a[(idx+i)%n] == i+1:\n\t\t\tpass\n\t\telse:\n\t\t\tcheck2=0\n\n\tif check1==1 or check2==1:\n\t\tprint(\"YES\")\n\telse:\n\t\tprint(\"NO\")", "passed": true, "time": 0.24, "memory": 14252.0, "status": "done"}, {"code": "from collections import deque\nfor _ in range(int(input())):\n    n = int(input())\n    A = list(map(int, input().split()))\n    ans = 'NO'\n    B = deque(A)\n    C = [i for i in range(1, n + 1)]\n    D = C[::-1]\n    for i in range(n):\n        B.popleft()\n        B.append(A[i])\n        if list(B) == C or list(B) == D:\n            ans = 'YES'\n    print(ans)", "passed": true, "time": 0.14, "memory": 14144.0, "status": "done"}, {"code": "q=int(input())\nfor i in range(q):\n    n=int(input())\n    arr=[int(x) for x in input().split()]\n    l=arr[0]\n    forwards=True\n    back=True\n    for j in range(n-1):\n        if arr[j]-1!=(arr[0]-1+j)%n:\n            forwards=False\n        if arr[j]-1!=(arr[0]-1-j)%n:\n            back=False\n    if forwards==True or back==True:\n        print(\"YES\")\n    else:\n        print(\"NO\")", "passed": true, "time": 0.86, "memory": 14164.0, "status": "done"}, {"code": "q = int(input())\nfor i in range(q):\n\tn = int(input())\n\tp = list(map(int, input().split()))\n\tfor i in range(n - 1):\n\t\tif p[i] + 1 != p[i+1] and not(p[i] == n and p[i+1] == 1):\n\t\t\tbreak\n\telse:\n\t\tprint('YES')\n\t\tcontinue\n\tfor i in range(n - 1):\n\t\tif p[i] - 1 != p[i+1] and not(p[i] == 1 and p[i+1] == n):\n\t\t\tbreak\n\telse:\n\t\tprint('YES')\n\t\tcontinue\n\tprint('NO')\n", "passed": true, "time": 0.24, "memory": 14288.0, "status": "done"}, {"code": "n=int(input())\nfor x in range(n):\n    t=int(input())\n    r=list(map(int,input().split()))\n    r=r+r\n    l1=[x for x in range(1,t+1)]\n    l2=l1[::-1]\n    bo=0\n    for i in range(t):\n        if(r[i:i+t]==l1):\n            bo=1\n        if(r[i:i+t]==l2):\n            bo=1\n    if(bo==1):\n        print(\"YES\")\n    else:\n        print(\"NO\")\n", "passed": true, "time": 0.14, "memory": 14224.0, "status": "done"}, {"code": "from sys import stdin\nq=int(stdin.readline().strip())\nfor i in range(q):\n    n=int(stdin.readline().strip())\n    s=list(map(int,stdin.readline().strip().split()))\n    x=s.index(1)\n    y=1\n    t=True\n    for i in range(n):\n        if s[x]!=y:\n            t=False\n            break\n        x=(x+1)%n\n        y+=1\n    t1=True\n    x=s.index(1)\n    y=1\n    for i in range(n):\n\n        if s[x]!=y:\n            t1=False\n            break\n        x=(x-1)%n\n        y+=1\n    if t or t1:\n        print(\"YES\")\n    else:\n        print(\"NO\")\n        \n", "passed": true, "time": 0.15, "memory": 14100.0, "status": "done"}, {"code": "for q in range(int(input())):\n    n = int(input())\n    a = [int(x) for x in input().split()]\n\n    idx = a.index(1)\n\n    b = a[idx : ] + a[ : idx]\n    c = a[ : idx + 1][::-1] + a[idx +1 : ][::-1]\n\n    a.sort()\n\n    if b == a or c == a:\n        print(\"YES\")\n    else:\n        print(\"NO\")\n", "passed": true, "time": 0.15, "memory": 14312.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    l = [*map(int, input().split())]\n    res = False\n    for i in range(n):\n        x = l[i:] + l[:i]\n        if all(x[i] < x[i + 1] for i in range(n - 1)) or all(x[i] > x[i + 1] for i in range(n - 1)):\n            res = True\n    print('YES' if res else 'NO')", "passed": true, "time": 0.86, "memory": 14292.0, "status": "done"}, {"code": "q = int (input())\nwhile q:\n    n = int(input())\n    a = list(map(int, input().split()))\n    a += a\n    p = [i for i in range(1, n + 1)]\n    flag = False\n    for i in range(n):\n        if a[i: i + n] == p or a[i: i + n] == p[::-1]:\n            print(\"YES\")\n            flag = True\n            break\n    if not flag:\n        print(\"NO\")\n    q -= 1\n", "passed": true, "time": 0.24, "memory": 14220.0, "status": "done"}, {"code": "for _ in range(int(input())):\n\tn = int(input())\n\tans = [i + 1 for i in range(n)]\n\tl = list(map(int, input().split()))\n\tone = l.index(1)\n\tl = l[one:] + l[:one]\n\trev = l[::-1]\n\tone = rev.index(1)\n\trev = rev[one:] + rev[:one]\n\tif rev == ans or l == ans:\n\t\tprint('YES')\n\telse:\n\t\tprint('NO')", "passed": true, "time": 0.14, "memory": 14384.0, "status": "done"}, {"code": "q = int(input())\nfor _ in range(q):\n    n = int(input())\n    p = list(map(int, input().split()))\n    i = p.index(1)\n    p2 = p[i:] + p[:i]\n    if p2 == list(range(1, n + 1)) or p2[1:] == list(reversed(list(range(2, n + 1)))):\n        print('YES')\n    else:\n        print('NO')\n", "passed": true, "time": 0.23, "memory": 14336.0, "status": "done"}, {"code": "t = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tc = list(map(int,input().split()))\n\tidx = 0\n\tf = 0\n\tf2 = 0\n\tfor i in range(n):\n\t\tif(c[i]==1):\n\t\t\tidx = i\n\t\t\tbreak\n\n\tfor i in range(n):\n\t\tif(c[(idx+i)%n]!=i+1):\n\t\t\tf = 1\n\t\tif(c[idx-i]!=i+1):\n\t\t\tf2 = 1\n\tif f == 1 and f2 ==1:\n\t\tprint('NO')\n\telse:\n\t\tprint('YES')", "passed": true, "time": 0.14, "memory": 14112.0, "status": "done"}, {"code": "n = int(input())\nfor _ in range(n):\n\t_ = int(input())\n\t*l, = map(int, input().split())\n\tans = False\n\tfor i in range(len(l)-1):\n\t\tif l[i] == len(l):\n\t\t\tif not l[i+1] == 1:\n\t\t\t\tbreak\n\t\telse:\n\t\t\tif not l[i] + 1 == l[i+1]:\n\t\t\t\tbreak\n\telse:\n\t\tans = True\n\tfor i in range(len(l)-1):\n\t\tif l[i] == 1:\n\t\t\tif not l[i+1] == len(l):\n\t\t\t\tbreak\n\t\telse:\n\t\t\tif not l[i] - 1 == l[i+1]:\n\t\t\t\tbreak\n\telse:\n\t\tans = True\n\tif ans:\n\t\tprint(\"YES\")\n\telse:\n\t\tprint(\"NO\")", "passed": true, "time": 0.14, "memory": 14136.0, "status": "done"}, {"code": "#579_A\n\nq = int(input())\n\nfor i in range(0, q):\n    n = int(input())\n    ln = [int(j) for j in input().split(\" \")]\n    st = 0\n    f = True\n    for j in range(1, len(ln)):\n        if abs(ln[j] - ln[j - 1]) != 1 and abs(ln[j] - ln[j - 1]) != n - 1:\n            f = False\n            break\n    if abs(ln[0] - ln[-1]) != 1 and abs(ln[0] - ln[-1]) != n - 1:\n        f = False\n    if f:\n        print(\"YES\")\n    else:\n        print(\"NO\")\n        \n", "passed": true, "time": 0.14, "memory": 14116.0, "status": "done"}, {"code": "import math\n# helpful:\n# r,g,b=map(int,input().split())\n#list1 = input().split()\n#for i in range(len(list1)):\n#    list1[i] = int(list1[i])\n#print(list1)\n# arr = [[0 for x in range(columns)] for y in range(rows)]\n\nq = int(input())\nfor i in range(q):\n    n = int(input())\n    arr = input().split()\n    for i in range(n):\n        arr[i] = int(arr[i])\n    if(n<=3):\n        print(\"YES\")\n    else:\n        havent = True\n        val = (arr[1]-arr[0]) % n\n        if(val != 1 and val != n-1):\n            print(\"NO\")\n        else:\n            for i in range(n-1):\n               if((arr[i+1]-arr[i]) % n != val and havent):\n                   print(\"NO\")\n                   havent = False\n            if(havent):\n               print(\"YES\")\n           \n        \n", "passed": true, "time": 0.14, "memory": 14352.0, "status": "done"}, {"code": "q = int(input())\nfor qq in range(q):\n    n = int(input())\n    *p, = list(map(int, input().split()))\n    for i in range(n-1):\n        if (p[i+1]-p[i]!=1 and not(p[i+1]==1 and p[i]==n)):\n            break\n    else:\n        print(\"YES\")\n        continue\n\n    for i in range(n-1):\n        if (p[i+1]-p[i]!=-1 and not(p[i+1]==n and p[i]==1)):\n            break\n    else:\n        print(\"YES\")\n        continue\n    \n    print(\"NO\")\n", "passed": true, "time": 0.14, "memory": 14200.0, "status": "done"}, {"code": "import sys\n\ndef solve(A):\n    n = len(A)\n    t = A[0]-1\n    cw = True\n    for a in A:\n        if t != a-1:\n            cw = False\n        t = (t+1)%n\n    t = A[0]-1\n    ccw = True\n    for a in A:\n        if t != a-1:\n            ccw = False\n        t = (n+t-1)%n\n    return (ccw or cw)\n\nin_file = sys.stdin #open(\"A.txt\", \"r\") \n\nq = int(in_file.readline().strip())\nfor _ in range(q):\n    n = int(in_file.readline().strip())\n    A = list(map(int, in_file.readline().strip().split()))\n    if solve(A):\n        sys.stdout.write(\"YES\\n\")\n    else:\n        sys.stdout.write(\"NO\\n\")\nsys.stdout.flush()", "passed": true, "time": 0.15, "memory": 14356.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    p = list(int(a) for a in input().split())\n    c = 0\n    if p[n-1] < p[0]:\n        c += 1\n    for i in range(1, n):\n        if p[i-1] < p[i]:\n            c += 1\n    if c == n-1 or c == 1:\n        print(\"YES\")\n    else:\n        print(\"NO\")", "passed": true, "time": 0.14, "memory": 14204.0, "status": "done"}, {"code": "\nq = int(input())\n\nfor i in range(q):\n    n = int(input())\n    p = list(map(int,input().split()))\n    q = p+p+p\n    p = sorted(p)\n    r = p[::-1]\n    f = 0\n    for k in range(2*n):\n        if q[k:k+n] == r or q[k:k+n] == p:\n            f = 1\n            break\n    if f == 0:\n        print(\"NO\")\n    else:\n        print(\"YES\")\n", "passed": true, "time": 0.14, "memory": 14136.0, "status": "done"}, {"code": "'''q=int(input())\nfor I in range(q):\n    n=int(input())\n    a=[int(i) for i in input().split()]\n    ind = a.find(1)\n    ini = [(i+1) for i in range(n)]\n    arr1 = a[ind:]\n    arr2 = a[:ind]\n    if(sorted(arr1)==a['''\n\ndef main():\n    t=int(input())\n    for q in range(t):\n        n = int(input())\n        a = [int(x) for x in input().split()]\n\n        idx = a.index(1)\n\n        b = a[idx : ] + a[ : idx]\n        c = a[ : idx + 1][::-1] + a[idx +1 : ][::-1]\n\n        a.sort()\n\n        if b == a or c == a:\n            print(\"YES\")\n        else:\n            print(\"NO\")\n\n\nmain()\n", "passed": true, "time": 0.14, "memory": 14260.0, "status": "done"}, {"code": "''' \u0628\u0650\u0633\u0652\u0645\u0650 \u0627\u0644\u0644\u064e\u0651\u0647\u0650 \u0627\u0644\u0631\u064e\u0651\u062d\u0652\u0645\u064e\u0670\u0646\u0650 \u0627\u0644\u0631\u064e\u0651\u062d\u0650\u064a\u0645\u0650 '''\n#codeforces1203A_live\ngi = lambda : list(map(int,input().split()))\nfor k in range(gi()[0]):\n\tn, = gi()\n\tl = gi()\n\tcl = l[l.index(1):] + l[:l.index(1)]\n\tccl = l[l.index(n):] + l[:l.index(n)]\n\tp = [i for i in range(1, n + 1)]\n\tif cl == p or ccl == p[::-1]:\n\t\tprint(\"YES\")\n\telse:\n\t\tprint(\"NO\")", "passed": true, "time": 0.13, "memory": 14360.0, "status": "done"}, {"code": "t = int(input())\n\nwhile t:\n    t -= 1\n    n = int(input())\n    arr = [int(item) for item in input().split(' ')]\n    ans = True\n    for i in range(n):\n        if (arr[i - 1] + 1) % n == arr[i] % n:\n            continue\n        ans = False\n        break\n\n    ans2 = True\n    for i in range(n):\n        if (arr[i] + 1) % n == arr[i - 1] % n:\n            continue\n        ans2 = False\n        break\n    print(\"YES\" if ans or ans2 else \"NO\")\n", "passed": true, "time": 0.17, "memory": 14364.0, "status": "done"}, {"code": "w = int(input())\ndef fun(x, n):\n\tif x % n != 0:\n\t\treturn x % n\n\telse:\n\t\treturn n\nfor we in range(w):\n\tn = int(input())\n\tl = list(map(int,input().split()))\n\tif n == 1:\n\t\tprint(\"YES\")\n\telse:\n\t\tstart = l[0]\n\t\todp = 1\n\t\tif l[1] == fun(l[0] + 1, n):\n\t\t\tfor i in range(1, n):\n\t\t\t\tif l[i] != fun(l[i-1] + 1, n):\n\t\t\t\t\todp = 0\n\t\t\t\t\tbreak\n\t\telif l[1] == fun(l[0] - 1, n):\n\t\t\tfor i in range(1, n):\n\t\t\t\tif l[i] != fun(l[i-1] - 1, n):\n\t\t\t\t\todp = 0\n\t\t\t\t\tbreak\n\t\telse:\n\t\t\todp = 0\n\t\tif odp == 0:\n\t\t\tprint(\"NO\")\n\t\telse:\n\t\t\tprint(\"YES\")", "passed": true, "time": 0.14, "memory": 14252.0, "status": "done"}, {"code": "for _ in range(int(input())):\n    n = int(input())\n    p = list(map(int, input().split()))\n    i = p.index(1)\n    if p[i:] + p[:i] == sorted(p) or p[i + 1:] + p[:i + 1] == sorted(p, reverse=True):\n        print(\"YES\")\n    else:\n        print(\"NO\")", "passed": true, "time": 0.14, "memory": 14252.0, "status": "done"}]