Shinju and the Lost Permutation

题意翻译

给出如下定义： - 排列 $p=[p_1,p_2,\cdots,p_n]$ 的第 $i$ 循环置换为 $p=[p_{n-i+1},\cdots,p_{n},p_1,p_2,\cdots,p_{n-i}]$。可以发现它仍然是一个排列。 - 对于一个排列 $p=[p_1,p_2,\cdots,p_n]$，假设有一个数组 $b=[b_1,b_2,\cdots,b_n]$，其中 $b_i=\max\limits_{1\leqslant j\leqslant i}p_j$，那么排列 $p$ 的权值为 $b$ 数组中出现的不同元素的个数。 现在，给定一个长度为 $n$ 的数组 $c=[c_1,c_2,\cdots,c_n]$，请判断是否存在一个 $1\sim n$ 的排列 $p$，使得对于所有的 $1\leqslant i\leqslant n$，$c_i$ 是排列 $p$ 的第 $i-1$ 循环置换的权值。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 5\times 10^3$。 - $1\leqslant n,\sum n\leqslant 10^5$。 - $1\leqslant c_i\leqslant n$。 Translated by Eason_AC

题目描述

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

输出样例 #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 $ .