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]$$$ 并且 $$$b$$$ 中有 $$$4$$$ 不同的元素。
不幸的是,Shinju 失去了排列$$$p$$$!她记得的唯一信息是一个数组 $$$c$$$,其中 $$$c_i$$$ 是排列 $$$p$$$ 的第 $$$(i-1)$$$ 次循环移位的幂。她也不确定自己是否记得正确,所以她想知道自己的记忆力是否足够好。
给定数组 $$$c$$$,确定是否存在与 $$$c$$$ 一致的排列 $$$p$$$。您不必构造排列$$$p$$$。
排列是一个数组,由 $$$n$$$ 不同的整数组成,从 $$$1$$$ 到 $$$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
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
注意
在第一个测试用例中,排列 $$$[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$$$ 的第一个循环移位是 $$$[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$$$ 的排列。