Description

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).

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

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$.