分数: 1200 点
问题陈述
有 N 盒子编号为 1 to N,和 N 球编号为 1 to N.
您已为 Snuke 分配了以下内容 程序 作为作业。
- 将每个球放入他喜欢的任何盒子中。同一个盒子里可以放多个球,也可以有没有球的盒子。
- 对于 i = 1, 2, \cdots, N 按此顺序执行以下操作。
- 如果框 i 不包含球,不执行任何操作。
- 如果框 i 包含球,将它们全部取出并排成一行 以他喜欢的任何顺序。让 k 是取出的球数,并且 (x_1, x_2, \cdots, x_k) 是该行中的球号。对于每个 1 \leq j \leq k, 放球 x_j 放入盒子 x_{j+1}。在这里, x_{k+1} 意味着 x_1。所有这些将球放入盒子的操作都是同时发生的。
他声称他已经完成了作业并向你报告最终状态。 具体来说,他说那个球 i 装在盒子里 A_i 手术后。
您怀疑他是否正确执行了该程序。 确定他报告的状态是否是该程序的可能结果。
有 T 每个输入的测试用例。
约束
- 1 \leq T \leq 250000
- 1 \leq N \leq 250000
- 1 \leq A_i \leq N
- 总和 N 每个输入中的所有测试用例最多 250000.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
T case_1 case_2 \vdots case_T
每个测试用例均按以下格式给出:
N A_1 A_2 \cdots A_N
输出
对于每个测试用例,打印 Yes 如果 Snuke 报告的状态是该过程的可能结果,并且 No 否则。
示例输入 1
5 3 1 1 1 3 2 2 2 5 1 2 3 4 5 10 8 3 8 10 1 5 3 1 6 4 10 1 5 1 2 4 8 8 6 7 3
示例输出 1
Yes No Yes No Yes
考虑第一个测试用例。
以下步骤产生 Snuke 报告的状态,所以答案是 Yes.
- 放球 1, 2, 3 放入盒子中 1, 1, 2。
- 从盒子里拿出球 1 并将它们排列为 (2, 1).
- 放球 2 放入盒子 1.
- 放球 1 放入盒子 2.
- 从盒子里拿出球 2 并将它们排列为 (1, 3).
- 放球 1 放入盒子 3.
- 放球 3 放入盒子 1.
- 从盒子里拿出球 3 并将它们排列为 (1).
- 放球 1 放入盒子 1.
- 现在,球 1, 2, 3 全部在盒子里 1.