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

输入格式

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

输出格式

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

输入输出样例 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

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