A14880. 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).
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).
输入格式
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$ .
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$ .
输出格式
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).
You can output "YES" and "NO" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).
输入输出样例
输入 #1
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
输出 #1
YES YES NO NO YES NO
说明/提示
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$ .
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$ .