You are an expert competitive programmer. You will be given a problem statement, test case constraints and example test inputs and outputs. Please reason step by step about the solution (that must respect memory and time limits), then provide a complete implementation in python3.

Your solution must read input from standard input (cin), write output to standard output (cout).
Do not include any debug prints or additional output.

Put your final solution within a single code block:
```python
<your code here>
```

Execution time limit: 1.0 seconds
Memory limit: 256.0 MB

# Problem
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 Format
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 Format
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$$$.

Now solve the problem and return the code.