C. Shinju and the Lost Permutationtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard outputShinju 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).InputThe 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.OutputFor 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).ExampleInput
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
NoteIn 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.
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

YES YES NO NO YES NO 
['constructive algorithms', 'math', '*1700']