CF1658C Shinju and the Lost Permutation

Shinju 非常喜欢排列！今天，她向 Juju 借来了一个排列 $p$ 来玩。 排列 $p$ 的第 $i$ 次循环移位是对排列的一种变换，即 $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$ 的“幂”为其前缀最大值数组 $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$）。

输入包含多组测试数据。第一行包含一个整数 $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$。

对于每个测试用例，如果存在一个满足数组 $c$ 的排列 $p$，输出 "YES"；否则输出 "NO"。 你可以用任意大小写输出 "YES" 和 "NO"（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为肯定回答）。

在第一个测试用例中，排列 $[1]$ 满足数组 $c$。 在第二个测试用例中，排列 $[2,1]$ 满足数组 $c$。 在第五个测试用例中，排列 $[5, 1, 2, 4, 6, 3]$ 满足数组 $c$。具体如下： - $p$ 的第 $0$ 次循环移位为 $[5, 1, 2, 4, 6, 3]$，其幂为 $2$，因为 $b = [5, 5, 5, 5, 6, 6]$，有 $2$ 个不同的元素——$5$ 和 $6$。 - $p$ 的第 $1$ 次循环移位为 $[3, 5, 1, 2, 4, 6]$，其幂为 $3$，因为 $b = [3, 5, 5, 5, 5, 6]$。 - $p$ 的第 $2$ 次循环移位为 $[6, 3, 5, 1, 2, 4]$，其幂为 $1$，因为 $b = [6, 6, 6, 6, 6, 6]$。 - $p$ 的第 $3$ 次循环移位为 $[4, 6, 3, 5, 1, 2]$，其幂为 $2$，因为 $b = [4, 6, 6, 6, 6, 6]$。 - $p$ 的第 $4$ 次循环移位为 $[2, 4, 6, 3, 5, 1]$，其幂为 $3$，因为 $b = [2, 4, 6, 6, 6, 6]$。 - $p$ 的第 $5$ 次循环移位为 $[1, 2, 4, 6, 3, 5]$，其幂为 $4$，因为 $b = [1, 2, 4, 6, 6, 6]$。 因此，$c = [2, 3, 1, 2, 3, 4]$。 在第三、第四和第六个测试用例中，可以证明不存在满足数组 $c$ 的排列。 由 ChatGPT 4.1 翻译