CF1658C.Shinju and the Lost Permutation

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

Shinju 非常喜欢排列！今天，她向 Juju 借来一个排列 $p$ 来玩耍。

排列 $p$ 的第 $i$ 个循环移位（cyclic shift）是一种对排列的变换，使得 $p = [p_1, p_2, \ldots, p_n]$ 变为 $p = [p_{n-i+1}, \ldots, p_n, p_1, p_2, \ldots, p_{n-i}]$。

我们定义排列 $p$ 的**幂值（power）**为该排列的前缀最大值数组 $b$ 中不同元素的个数。前缀最大值数组 $b$ 是一个长度为 $n$ 的数组，满足 $b_i = \max(p_1, p_2, \ldots, p_i)$。例如，排列 $[1, 2, 5, 4, 6, 3]$ 的幂值为 $4$，因为其前缀最大值数组为 $b = [1, 2, 5, 5, 6, 6]$，其中包含 $4$ 个不同的元素。

不幸的是，Shinju 弄丢了排列 $p$！她唯一记得的信息是一个数组 $c$，其中 $c_i$ 表示排列 $p$ 的第 $(i-1)$ 个循环移位的幂值。但她对自己记忆的准确性并不确信，因此她想知道自己的记忆是否足够可靠。

给定数组 $c$，请判断是否存在一个排列 $p$，使得其所有循环移位的幂值恰好构成数组 $c$。你不需要构造出这样的排列 $p$。

排列是指由 $1$ 到 $n$ 的 $n$ 个互不相同的整数以任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（数字 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

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

输入包含多个测试用例。第一行包含一个整数 $t$（$1 \leq t \leq 5 \cdot 10^3$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

每个测试用例的第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$（$1 \leq c_i \leq n$）。

保证所有测试用例的 $n$ 之和不超过 $10^5$。

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

对于每个测试用例，如果存在一个排列 $p$ 满足数组 $c$，则输出 "YES"；否则输出 "NO"。

你可以以任意大小写形式输出 "YES" 和 "NO"（例如，字符串 "yEs"、"yes"、"Yes" 和 "YES" 均被视为肯定回答）。

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

在第一个测试用例中，排列 $[1]$ 满足数组 $c$。

在第二个测试用例中，排列 $[2,1]$ 满足数组 $c$。

在第五个测试用例中，排列 $[5, 1, 2, 4, 6, 3]$ 满足数组 $c$。下面我们说明其正确性。

• $p$ 的第零次循环移位为 $[5, 1, 2, 4, 6, 3]$。其“幂”为 $2$，因为此时 $b = [5, 5, 5, 5, 6, 6]$，其中包含 $2$ 个不同元素——$5$ 和 $6$。
• $p$ 的第一次循环移位为 $[3, 5, 1, 2, 4, 6]$。其“幂”为 $3$，因为此时 $b=[3,5,5,5,5,6]$。
• $p$ 的第二次循环移位为 $[6, 3, 5, 1, 2, 4]$。其“幂”为 $1$，因为此时 $b=[6,6,6,6,6,6]$。
• $p$ 的第三次循环移位为 $[4, 6, 3, 5, 1, 2]$。其“幂”为 $2$，因为此时 $b=[4,6,6,6,6,6]$。
• $p$ 的第四次循环移位为 $[2, 4, 6, 3, 5, 1]$。其“幂”为 $3$，因为此时 $b = [2, 4, 6, 6, 6, 6]$。
• $p$ 的第五次循环移位为 $[1, 2, 4, 6, 3, 5]$。其“幂”为 $4$，因为此时 $b = [1, 2, 4, 6, 6, 6]$。

因此，$c = [2, 3, 1, 2, 3, 4]$。

在第三个、第四个和第六个测试用例中，可以证明不存在满足数组 $c$ 的排列。