Shinju loves permutations very much! Today, she has borrowed a permutation $p$ from Juju to play with.

The $i$-th cyclic shift of a permutation $p$ is a transformation on the permutation such that $p = [p_1, p_2, \ldots, p_n] $ will now become $ p = [p_{n-i+1}, \ldots, p_n, p_1,p_2, \ldots, p_{n-i}]$.

Let's define the power of permutation $p$ as the number of distinct elements in the prefix maximums array $b$ of the permutation. The prefix maximums array $b$ is the array of length $n$ such that $b_i = \max(p_1, p_2, \ldots, p_i)$. For example, the power of $[1, 2, 5, 4, 6, 3]$ is $4$ since $b=[1,2,5,5,6,6]$ and there are $4$ distinct elements in $b$.

Unfortunately, Shinju has lost the permutation $p$! The only information she remembers is an array $c$, where $c_i$ is the power of the $(i-1)$-th cyclic shift of the permutation $p$. She's also not confident that she remembers it correctly, so she wants to know if her memory is good enough.

Given the array $c$, determine if there exists a permutation $p$ that is consistent with $c$. You do not have to construct the permutation $p$.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3, 4]$ is also not a permutation ($n=3$ but there is $4$ in the array).


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \leq t \leq 5 \cdot 10^3$) — the number of test cases.

The first line of each test case contains an integer $n$ ($1 \le n \le 10^5$).

The second line of each test case contains $n$ integers $c_1,c_2,\ldots,c_n$ ($1 \leq c_i \leq n$).

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.


-----Output-----

For each test case, print "YES" if there is a permutation $p$ exists that satisfies the array $c$, and "NO" otherwise.

You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).


-----Examples-----

Input
6
1
1
2
1 2
2
2 2
6
1 2 4 6 3 5
6
2 3 1 2 3 4
3
3 2 1
Output
YES
YES
NO
NO
YES
NO


-----Note-----

In the first test case, the permutation $[1]$ satisfies the array $c$.

In the second test case, the permutation $[2,1]$ satisfies the array $c$.

In the fifth test case, the permutation $[5, 1, 2, 4, 6, 3]$ satisfies the array $c$. Let's see why this is true.

The zeroth cyclic shift of $p$ is $[5, 1, 2, 4, 6, 3]$. Its power is $2$ since $b = [5, 5, 5, 5, 6, 6]$ and there are $2$ distinct elements — $5$ and $6$.

The first cyclic shift of $p$ is $[3, 5, 1, 2, 4, 6]$. Its power is $3$ since $b=[3,5,5,5,5,6]$.

The second cyclic shift of $p$ is $[6, 3, 5, 1, 2, 4]$. Its power is $1$ since $b=[6,6,6,6,6,6]$.

The third cyclic shift of $p$ is $[4, 6, 3, 5, 1, 2]$. Its power is $2$ since $b=[4,6,6,6,6,6]$.

The fourth cyclic shift of $p$ is $[2, 4, 6, 3, 5, 1]$. Its power is $3$ since $b = [2, 4, 6, 6, 6, 6]$.

The fifth cyclic shift of $p$ is $[1, 2, 4, 6, 3, 5]$. Its power is $4$ since $b = [1, 2, 4, 6, 6, 6]$.

Therefore, $c = [2, 3, 1, 2, 3, 4]$.

In the third, fourth, and sixth testcases, we can show that there is no permutation that satisfies array $c$.

Difficulty: MEDIUM_HARD
Tags: Mathematics

Constructive algorithms

Starter code:

Solutions:
def solve():
	if arr.count(1) != 1:
		return 'NO'
	for i in range(n - 1):
		if arr[i + 1] - arr[i] > 1:
			return 'NO'
	if arr[0] - arr[-1] > 1:
		return 'NO'
	return 'YES'
from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	print(solve())


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(1) != 1:
		print('NO')
		continue
	a += [a[0]]
	ok = True
	for i in range(0, n):
		if a[i + 1] - a[i] > 1:
			ok = False
			break
	print('YES' if ok else 'NO')


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	data = list(map(int, input().split()))
	num = data.count(1)
	if num == 0 or num > 1:
		print('NO')
	else:
		idx = data.index(1)
		data = data[idx:] + data[:idx]
		flag = 0
		for i in range(len(data) - 1):
			if data[i + 1] - data[i] > 1:
				flag = 1
				break
		if flag:
			print('NO')
		else:
			print('YES')


def main():
	t = int(input())
	for i in range(t):
		n = int(input())
		c = [int(num) for num in input().split(' ')]
		if c.count(1) != 1:
			print('NO')
			continue
		no = False
		c.append(c[0])
		for i in range(1, n + 1):
			if c[i] - c[i - 1] > 1:
				no = True
				break
		print('NO' if no else 'YES')
main()


import sys
input = sys.stdin.readline

def solve(n, c):
	idx = 0
	cnt = 0
	for i in range(n):
		if c[i] == 1:
			idx = i
			cnt += 1
	if cnt != 1:
		print('NO')
		return
	arr = c[idx:] + c[:idx]
	cnt = n
	prev = arr[0]
	for i in range(n - 1):
		if arr[i] >= arr[i + 1]:
			cnt -= arr[i] - prev + 1
			prev = arr[i + 1]
	cnt -= arr[-1] - prev + 1
	print('YES') if cnt == 0 else print('NO')
for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	solve(n, c)


from sys import stdin
input = stdin.readline

def get_string():
	return stdin.readline().strip()

def main():
	for _ in range(int(input())):
		n = int(input())
		c = list(map(int, input().split()))
		if c.count(1) != 1:
			print('NO')
			continue
		c.append(c[0])
		ans = True
		for i in range(n):
			if c[i + 1] - c[i] > 1:
				ans = False
		print('YES' if ans else 'NO')
main()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	data = list(map(int, input().split()))
	num = data.count(1)
	if num != 1:
		print('NO')
		continue
	data.append(data[0])
	flag = 0
	for i in range(len(data) - 1):
		if data[i + 1] - data[i] > 1:
			flag = 1
			break
	if flag:
		print('NO')
	else:
		print('YES')


(a, b, c) = (input, int, range)
for _ in c(b(a())):
	n = b(a())
	m = list(map(b, a().split()))
	print('YNEOS'[m.count(1) != 1 or m[0] > m[-1] + 1 or any((m[i + 1] - m[i] > 1 for i in range(n - 1)))::2])


a = int(input())
for i in range(a):
	x = int(input())
	y = [int(j) for j in input().split()]
	c1 = 0
	ind = -1
	if x == 1:
		print('YES')
		continue
	for j in range(x):
		if y[j] == 1:
			c1 = c1 + 1
			ind = j
	if c1 != 1:
		print('NO')
		continue
	f = 0
	ny = y[ind:] + y[0:ind]
	for j in range(x - 1):
		if ny[j + 1] > ny[j] + 1:
			f = 1
			break
	print('NO' if f == 1 else 'YES')


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	if l.count(1) != 1:
		print('NO')
	else:
		c = True
		for j in range(1, n):
			if l[j] - l[j - 1] > 1:
				print('NO')
				c = False
				break
		if l[0] - l[n - 1] > 1 and c:
			print('NO')
			c = False
		if c:
			print('YES')


def solver():
	m = int(input())
	for _ in range(m):
		n = int(input())
		f = list(map(int, input().split()))
		done = False
		count_of_1 = 0
		for i in range(n):
			if not done:
				if f[(i + 1) % n] - f[i] > 1 or (f[i] == n and f[(i + 1) % n] != 1):
					done = True
					print('NO')
				if f[i] == 1:
					count_of_1 += 1
		if not done:
			if count_of_1 == 1:
				print('YES')
			else:
				print('NO')
solver()


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	if n == 1:
		print('YES')
		continue
	if a.count(1) != 1:
		print('NO')
		continue
	id = a.index(1)
	key = 0
	for i in range(id + 1, n):
		if a[i] - a[i - 1] > 1:
			key = 1
			break
	if key == 0:
		if a[0] - a[-1] > 1:
			key = 1
	if key == 0:
		for i in range(1, id):
			if a[i] - a[i - 1] > 1:
				key = 1
				break
	if key == 0:
		print('YES')
	else:
		print('NO')


t = int(input())
while t:
	l = int(input())
	s = list(map(int, input().split()))
	if s.count(1) != 1:
		print('NO')
	else:
		flag = 0
		o = s.index(1)
		s = s[o:] + s[:o]
		for i in range(1, l):
			if s[i] > s[i - 1] and s[i] - s[i - 1] > 1:
				flag = 1
				break
		if flag == 1:
			print('NO')
		else:
			print('YES')
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(c) for c in input().split()]
	if 1 not in a or a.count(1) > 1:
		print('NO')
		continue
	i = a.index(1)
	b = a[i:] + a[:i]
	j = 1
	flag = True
	while j < n:
		if b[j] > b[j - 1] + 1:
			print('NO')
			flag = False
			break
		j += 1
	if flag:
		print('YES')


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	flag = 0
	k = 0
	for i in range(n):
		if A[i] == 1:
			flag += 1
			k = i
	if flag == 0 or flag > 1:
		print('NO')
		return
	C = A[k:] + A[:k]
	for i in range(1, n):
		if C[i] <= C[i - 1]:
			continue
		if C[i] > C[i - 1] + 1:
			print('NO')
			return
	print('YES')
t = int(input())
while t != 0:
	solve()
	t -= 1


def solve(a):
	(o, p) = (False, a[-1])
	for i in a:
		if i == 1:
			if o:
				return False
			o = True
		elif i - p > 1:
			return False
		p = i
	return o
for i in range(int(input())):
	length = input()
	print('YES' if solve([int(i) for i in input().split()]) else 'NO')


for q in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	flag = 0
	if arr.count(1) != 1:
		print('NO')
		continue
	flag = 0
	arr.append(arr[0])
	for i in range(1, n + 1):
		if arr[i] - arr[i - 1] > 1:
			flag = 1
			break
	if flag:
		print('NO')
	else:
		print('YES')


(a, b, c, d, e) = (input, print, int, False, True)
for i in range(c(a())):
	a()
	(r, x, y) = (e, list(map(c, a().split())), d)
	z = x[-1]
	for i in x:
		if i == 1:
			if y:
				r = d
				break
			else:
				y = e
		elif i - z > 1:
			r = d
			break
		z = i
	b('YNEOS'[not r & y::2])


x = int(input().strip())
for i in range(x):
	b = int(input().strip())
	a = list(map(int, input().strip().split()))
	if 1 not in a or a.count(1) > 1:
		print('NO')
	else:
		for i in range(b):
			if a[i] - a[i - 1] > 1:
				print('NO')
				break
		else:
			print('YES')


t = int(input())
for _ in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	if lst.count(1) != 1:
		print('NO')
		continue
	lst.append(lst[0])
	f = 1
	for i in range(n):
		if lst[i + 1] - lst[i] > 1:
			print('NO')
			f = 0
			break
	if f:
		print('YES')


T = int(input())
for _ in range(T):
	n = int(input())
	S = list(map(int, input().split()))
	if S.count(1) != 1:
		print('NO')
		continue
	S.append(S[0])
	flag = True
	for i in range(n):
		if S[i + 1] - S[i] > 1:
			flag = False
			break
	if flag:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	f = 0
	if l.count(1) != 1:
		print('NO')
		continue
	l.append(l[0])
	for i in range(n):
		if l[i + 1] - l[i] > 1:
			f = 1
			break
	print('YES' if f == 0 else 'NO')


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	w = 0
	if c.count(1) != 1:
		w = 1
	else:
		for i in range(n - 1):
			if c[i] == n and c[i + 1] != 1:
				w = 1
				break
			elif c[i] == 1 and c[i + 1] != 2:
				w = 1
				break
			elif c[i + 1] - c[i] > 1:
				w = 1
			if w == 1:
				break
		if c[0] - c[n - 1] > 1:
			w = 1
	if w == 1:
		print('NO')
	else:
		print('YES')


import sys
import math
data = sys.stdin.readlines()
numCases = int(data[0])
cases = []
for each in range(1, numCases + 1):
	input_ = data[each * 2].replace('\n', '')
	temp = input_.split(' ')
	array = []
	for each in temp:
		array.append(int(each))
	cases.append(array)
for case in cases:
	array = case
	if 1 not in array or array.count(1) > 1:
		print('NO')
		continue
	for ind in range(len(array)):
		if array[ind] - array[ind - 1] > 1:
			print('NO')
			break_ = True
			break
	else:
		print('YES')


t = int(input())

def main():
	n = int(input())
	a = [int(_) for _ in input().split(' ')]
	if n == 1:
		return 'YES'
	foundn = False
	found1 = 0
	for i in range(1, n + 1, 1):
		if i < n:
			pre = a[i - 1]
			now = a[i]
		else:
			pre = a[n - 1]
			now = a[0]
		if pre == n:
			if now != 1:
				return 'NO'
			continue
		if pre == 1:
			found1 += 1
			if now != 2:
				return 'NO'
			continue
		if now == 1:
			if pre < 2:
				return 'NO'
			continue
		if now == n:
			if pre != n - 1:
				return 'NO'
			continue
		if now - pre > 1:
			return 'NO'
	if found1 != 1:
		return 'NO'
	return 'YES'
while t:
	t -= 1
	print(main())


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	if a.count(1) != 1:
		print('NO')
		return
	a.append(a[0])
	for i in range(n):
		if a[i + 1] - a[i] > 1:
			print('NO')
			return
	print('YES')
tst = int(input())
for i in range(tst):
	solve()


for t in range(int(input())):
	n = int(input())
	lks = list(map(int, input().split()))
	cnt = 0
	for x in lks:
		if x == 1:
			cnt += 1
	if cnt != 1:
		print('NO')
	else:
		lks.append(lks[0])
		ok = False
		for i in range(0, n):
			if lks[i + 1] - lks[i] > 1:
				ok = True
				break
		if ok:
			print('NO')
		else:
			print('YES')


def exist(nums):
	n = len(nums)
	total1 = 0
	for i in range(n):
		if nums[i] == 1:
			total1 += 1
		if nums[i] - nums[i - 1] > 1:
			return False
	return total1 == 1
t = int(input())
for _ in range(t):
	_ = input()
	nums = [int(x) for x in input().split()]
	if exist(nums):
		print('YES')
	else:
		print('NO')


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	if 1 not in arr:
		out += 'NO\n'
		continue
	i = arr.index(1)
	arr = [*arr[i:], *arr[:i]]
	ans = 'NO\n'
	for i in range(1, len(arr)):
		if arr[i] < 2 or arr[i] > arr[i - 1] + 1:
			break
	else:
		ans = 'YES\n'
	out += ans
print(out)


import sys
t = int(sys.stdin.readline())
for _ in range(t):
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	flag = 1
	for i in range(1, n):
		if a[i] - a[i - 1] > 1:
			flag = 0
			break
	if flag and a.count(1) == 1:
		if n > 1 and a[0] - a[-1] > 1:
			print('NO')
		else:
			print('YES')
	else:
		print('NO')


def ss(n, l):
	if l.count(1) != 1:
		return False
	l.append(l[0])
	for i in range(1, n + 1):
		if l[i] - l[i - 1] > 1:
			return False
	return True
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	if ss(n, l):
		print('YES')
	else:
		print('NO')


from collections import deque
t = int(input())
for pp in range(t):
	n = int(input())
	lis = list(map(int, input().split()))
	sussy = sorted(lis)
	if sussy[0] != 1:
		print('NO')
		continue
	elif len(sussy) > 1 and sussy[0] == sussy[1] == 1:
		print('NO')
		continue
	d = deque(lis)
	while d[0] != 1:
		sus = d.popleft()
		d.append(sus)
	lis = list(d)
	suss = False
	for i in range(1, len(lis)):
		if lis[i] > lis[i - 1] + 1:
			print('NO')
			suss = True
			break
	if suss:
		continue
	print('YES')


def check_jump_and_drop(num):
	x = num + num
	index_of_1 = -1
	for (index, n) in enumerate(x):
		if n == 1:
			index_of_1 = index
			break
	if index_of_1 == -1:
		return False
	for i in range(index_of_1 + 1, len(x)):
		if x[i] == 1 and i != index_of_1 + len(num) or x[i] - 1 > x[i - 1]:
			return False
	return True

def topological(num):
	return True
t = int(input())
for _ in range(t):
	n = int(input())
	num = list(map(int, input().split()))
	if not check_jump_and_drop(num):
		print('NO')
	elif topological(num):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	for i in range(n):
		if l[i] == 1:
			l = [*l[i:], *l[:i]]
			break
	if l[0] != 1:
		print('NO')
	else:
		isBroken = False
		for i in range(1, n):
			if l[i - 1] < l[i]:
				if l[i] - l[i - 1] > 1:
					isBroken = True
					break
			elif l[i] <= 1:
				isBroken = True
				break
		if isBroken:
			print('NO')
		else:
			print('YES')


import sys
import string
from decimal import Decimal
from math import log

def inp():
	return int(input())

def inplist():
	return list(map(int, input().split()))

def inpstrlist():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
t = int(input())
for _ in range(t):
	n = inp()
	arr = inplist()
	if arr.count(1) != 1:
		print('NO')
		continue
	idx = arr.index(1)
	f = True
	arr.append(arr[0])
	for i in range(n):
		if arr[i + 1] - arr[i] > 1:
			f = False
			break
	if f:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	(a, b) = (l.count(1), l.count(n))
	co = True
	if a != 1 or b > 1:
		co = False
	else:
		for i in range(n - 1):
			if l[i] == 1 and l[i + 1] != 2:
				co = False
				break
			elif l[i] == n and l[i + 1] != 1:
				co = False
				break
			elif l[i + 1] - l[i] > 1:
				co = False
				break
		if l[0] - l[-1] > 1:
			co = False
	if co:
		print('YES')
	else:
		print('NO')


class Solution:

	def solve(self, c):
		count = 0
		for i in c:
			if i == 1:
				count += 1
				if count > 1:
					return 'NO'
		if count == 0:
			return 'NO'
		c.append(c[0])
		for i in range(len(c) - 1):
			if c[i + 1] - c[i] > 1:
				return 'NO'
		return 'YES'
T = int(input())
while T:
	T -= 1
	n = int(input())
	c = input().split(' ')
	for i in range(n):
		c[i] = int(c[i])
	print(Solution().solve(c))


t = int(input())
for test in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	if min(c) != 1:
		print('NO')
		continue
	i = c.index(1)
	new_c = c
	if i > 0:
		new_c = c[i:] + c[:i]
	ans = 'YES'
	for j in range(n - 1):
		if new_c[j + 1] - new_c[j] == 1:
			continue
		elif new_c[j + 1] <= new_c[j] and new_c[j + 1] >= 2:
			continue
		else:
			ans = 'NO'
			break
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	numb = []
	for j in range(n):
		if c[j] == 1:
			numb.append(j)
	if len(numb) != 1:
		print('NO')
	else:
		numb = numb[0]
		u = 0
		for i in range(n - 1):
			a = c[(i + numb) % n]
			b = c[(i + 1 + numb) % n]
			if b > a + 1:
				print('NO')
				u = 1
				break
		if not u:
			print('YES')


T = int(input())
for t in range(T):
	n = int(input())
	c = list(map(int, input().split()))
	if c.count(1) != 1:
		print('NO')
	else:
		possible = True
		prev = c.index(1)
		for i in range(n - 1):
			curr = (prev + 1) % n
			if c[curr] - c[prev] > 1:
				print('NO')
				possible = False
				break
			prev = curr
		if possible:
			print('YES')


tc = int(input())
for _ in range(tc):
	n = int(input())
	a = list(map(int, input().split()))
	s = set(a)
	mi = min(s)
	ma = max(s)
	if n == 1:
		print('YES')
	elif mi != 1 or ma == 1 or len(s) != ma or (a.count(1) != 1):
		print('NO')
	else:
		for i in range(-1, n - 1):
			if a[i + 1] - a[i] > 1:
				print('NO')
				break
		else:
			print('YES')


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	err = 0
	if n == 2:
		if lst != [1, 2] and lst != [2, 1]:
			err += 1
	else:
		for j in range(1, n):
			if lst[j] > lst[j - 1]:
				if lst[j] - lst[j - 1] > 1:
					err += 1
					break
	if lst.count(1) > 1 or 1 not in lst:
		err += 1
	if lst[0] > lst[-1]:
		if lst[0] - lst[-1] > 1:
			err += 1
	if err == 0:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	(cnt, flag) = (0, 1)
	for i in range(n):
		cnt += c[i] == 1
		if c[i] - c[i - 1] > 1:
			flag = False
	print('YES' if flag and cnt == 1 else 'NO')


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	one = c.count(1)
	if one != 1:
		print('NO')
	else:
		ione = c.index(1)
		l = c[ione:] + c[0:ione]
		flage = 0
		for i in range(1, n):
			if l[i] > l[i - 1] and l[i] - l[i - 1] > 1:
				flage = 1
				break
		if flage == 1:
			print('NO')
		else:
			print('YES')


def lostperm(C):
	if C == [1]:
		return True
	else:
		ct = 0
		maxdiff = 0
		for i in range(len(C)):
			if C[i] == 1:
				ct += 1
			if i == 0:
				temp = C[i] - C[-1]
			else:
				temp = C[i] - C[i - 1]
			maxdiff = max(maxdiff, temp)
		if ct != 1 or maxdiff != 1:
			return False
		else:
			return True
t = int(input())
for x in range(t):
	n = int(input())
	C = [int(s) for s in input().split()]
	res = lostperm(C)
	if res:
		print('YES')
	else:
		print('NO')


T = int(input())
for j in range(T):
	tmp1 = input()
	goal_array = list(map(int, input().split(' ')))
	for i in range(len(goal_array)):
		if goal_array[i] == 1:
			goal_array = goal_array[i:] + goal_array[0:i]
			break
	if goal_array[0] != 1:
		print('NO')
	else:
		answer = True
		for i in range(1, len(goal_array)):
			if goal_array[i] > goal_array[i - 1] + 1:
				print('NO')
				answer = False
				break
			elif goal_array[i] == 1:
				print('NO')
				answer = False
				break
		if answer == True:
			print('YES')


mod = 998244353
T = int(input())
for tt in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	flag = 1
	cnt = 0
	for i in range(1, n, 1):
		if a[i] > a[i - 1] and a[i] - a[i - 1] > 1:
			flag = 0
	if a[0] > a[n - 1] + 1 and a[0] - a[n - 1] > 1:
		flag = 0
	for i in range(n):
		if a[i] == 1:
			cnt += 1
	if flag and cnt == 1:
		print('YES')
	else:
		print('NO')


import sys
import math
from bisect import bisect_right as br
from collections import deque
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for i in range(int(input())):
	n = int(input())
	arr = int_arr()
	if arr.count(1) != 1:
		print('NO')
		continue
	arr.append(arr[0])
	for i in range(1, n + 1):
		if arr[i] > arr[i - 1] and arr[i] - arr[i - 1] > 1:
			print('NO')
			break
	else:
		print('YES')


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	fin_arr = []
	tmp = []
	last = -1
	for (idx, i) in enumerate(arr):
		if i != 1:
			tmp.append(i)
		else:
			last = idx
			break
	arr = arr[idx:] + tmp
	if arr[0] != 1:
		print('NO')
		continue
	prev = arr[0]
	no = False
	for i in range(1, n):
		if arr[i] == 1 or arr[i] > arr[i - 1] + 1:
			no = True
			break
	if no:
		print('NO')
	else:
		print('YES')


N = len
M = list
L = range
I = 'NO'
H = input
G = int
D = print
from collections import deque
J = G(H())
for O in L(J):
	P = G(H())
	A = M(map(G, H().split()))
	B = sorted(A)
	if B[0] != 1:
		D(I)
		continue
	elif N(B) > 1 and B[0] == B[1] == 1:
		D(I)
		continue
	C = deque(A)
	while C[0] != 1:
		K = C.popleft()
		C.append(K)
	A = M(C)
	E = False
	for F in L(1, N(A)):
		if A[F] > A[F - 1] + 1:
			D(I)
			E = True
			break
	if E:
		continue
	D('YES')


from collections import Counter, defaultdict, deque, namedtuple
from functools import lru_cache
from typing import List, Dict
import bisect as b
import heapq as h
import math as m

def inti():
	return int(input())

def ints():
	return [int(x) for x in input().split()]

def main_tc():
	n = inti()
	numbers = ints()
	one_count = 0
	one_index = None
	for i in range(len(numbers)):
		if numbers[i] == 1:
			one_count += 1
			one_index = i
	if one_count != 1:
		print('NO')
		return
	new_numbers = numbers[one_index:] + numbers[:one_index]
	for i in range(len(new_numbers) - 1):
		if new_numbers[i + 1] - new_numbers[i] > 1:
			print('NO')
			return
	print('YES')

def main():
	tc = inti()
	for _ in range(tc):
		main_tc()
main()


t = int(input())
for _ in range(t):
	n = int(input())
	c = list(map(int, input().split()))
	mp = {}
	for i in range(n):
		mp[c[i]] = i
	if mp.get(1) is None or c.count(1) > 1:
		print('NO')
		continue
	p = mp[1]
	flag = 0
	c = c[p:] + c[0:p]
	for i in range(1, n):
		if c[i] - c[i - 1] > 1:
			flag = 1
	if flag == 1:
		print('NO')
	else:
		print('YES')


import sys
input = lambda : sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
t = int(input())
for _ in [0] * t:
	n = int(input())
	c = list(map(int, input().split()))
	ans = 'YES'
	if max(c) != len(set(c)) or c.count(1) != 1:
		ans = 'NO'
	for (i, j) in zip(c + c, c[1:] + c):
		if j > i and j > i + 1:
			ans = 'NO'
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	c = [int(x) for x in input().split(' ')]
	ones = 0
	last_one_idx = 0
	has_greater_n = False
	for (i, ci) in enumerate(c):
		if ci == 1:
			ones += 1
			last_one_idx = i
		if ci > n:
			has_greater_n = True
	if ones != 1 or has_greater_n:
		print('NO')
		continue
	passsed = 0
	idx = last_one_idx
	is_valid = True
	while passsed < n:
		passsed += 1
		diff = c[(idx + 1) % n] - c[idx % n]
		if diff > 0 and diff != 1:
			is_valid = False
			break
		idx = (idx + 1) % n
	if is_valid:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	k = arr.count(1)
	if k != 1:
		print('NO')
	else:
		k = arr.index(1)
		arr2 = []
		for i in range(n):
			arr2.append(arr[(k + i) % n])
		c = 0
		for i in range(n - 1):
			if arr2[i + 1] - arr2[i] > 1:
				c = 1
		if c == 1:
			print('NO')
		else:
			print('YES')


for _ in range(int(input())):
	n = int(input())
	c = list(map(int, input().split()))
	i = 0
	flag = 1
	while i < n and c[i] != 1:
		i += 1
	if i == n:
		flag = 0
	j = i
	i += 1
	while i < n:
		if c[i] - c[i - 1] >= 2 or c[i] == 1 or c[i] > i - j + 1:
			flag = 0
		i += 1
	i = 0
	while i < j:
		if c[i] - c[i - 1] >= 2 or c[i] == 1 or c[i] > n - j + i + 2:
			flag = 0
		i += 1
	if flag == 1:
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n = int(input())
	c = list(map(int, input().split(' ')))
	yesval = False
	curval = 0
	for theta in range(n):
		if c[theta] == 1:
			yesval = True
			curval = theta
			break
	if not yesval:
		print('NO')
	else:
		for delta in range(1, n):
			temp = (curval + delta) % n
			prev = (curval + delta - 1) % n
			if delta == 1:
				if c[temp] != 2:
					yesval = False
					break
			if c[temp] - c[prev] > 1:
				yesval = False
				break
			if c[temp] <= 1:
				yesval = False
				break
		if not yesval:
			print('NO')
		else:
			print('YES')


from calendar import c
import sys
import math
T = int(input())
for _ in range(T):
	n = int(input())
	arr = [int(i) for i in input().split()]
	x = min(range(len(arr)), key=arr.__getitem__)
	if arr[x] == 1:
		p = 1
		ok = True
		for i in range(1, n):
			x = (x + 1) % n
			if arr[x] < 2 or arr[x] > p + 1:
				ok = False
				break
			p = arr[x]
		if ok:
			print('YES')
		else:
			print('NO')
	else:
		print('NO')


import sys
T = int(sys.stdin.readline().strip())
for t in range(T):
	n = int(sys.stdin.readline().strip())
	arr = [int(x) for x in sys.stdin.readline().strip().split(' ')]
	flag = 1
	if 1 not in arr:
		flag = 0
	else:
		for (i, x) in enumerate(arr):
			if i == n - 1:
				y = arr[0]
			else:
				y = arr[i + 1]
			if y > x + 1:
				flag = 0
				break
		if len(arr) > 1:
			cnt = {}
			for x in arr:
				if x not in cnt:
					cnt[x] = 0
				cnt[x] += 1
			if cnt[1] != 1:
				flag = 0
			else:
				p = 1
				q = max(arr)
				while p <= q:
					if p not in cnt:
						flag = 0
						break
					p += 1
	print('YES' if flag else 'NO')