← 返回题目列表

AtCoder · arc211_e

E. 贪婪的高桥2

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

给你一个正整数 N 和排列 P of (1,2,\dots,N).

当有一棵树 N 顶点编号 1,2,\dots,N,Snuke和Takahashi按照以下规则移动:

  • Snuke 指定了一个排列 Q of (1,2,\dots,N) 使得高桥返回的序列在遵循以下规则时在字典顺序上是最大的。
  • 高桥,位于顶点 树的 1 ,首先接收 Q 并初始化一个整数序列 R 的长度-1 序列 (Q_1)。然后,他动了 N-1 次如下,并返回最终的 R:
    • 访问顶点 i 最小 Q_i 与先前访问过的顶点相邻但尚未访问过的顶点(可以证明总是存在一个这样的顶点)。然后,追加 Q_i 到结束 R.

这里,顶点 1 被认为最初已被访问。

判断是否存在让Takahashi返回的树 P.

你被给予 T 测试用例;解决它们中的每一个。

约束

  • 1 \le T \le 10^5
  • 1 \le N \le 2 \times 10^5
  • P 是一个排列 (1,2,\dots,N).
  • 总和 N 所有测试用例最多 2 \times 10^5.
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

T
\text{case}_1
\text{case}_2
\vdots
\text{case}_T

每个测试用例均按以下格式给出:

N
P_1 P_2 \ldots P_N

输出

输出 T 行。

的 i- 第行应包含 Yes 如果存在满足条件的树 i- 第一个测试用例,以及 No 否则。


示例输入 1

3
4
4 2 3 1
4
4 1 3 2
11
11 8 9 6 7 10 3 4 5 1 2

示例输出 1

Yes
No
Yes

对于第一个测试用例,具有四个顶点的树,顶点之间有边 1-2, 1-3,和 2-4 满足条件。

如果 Snuke 指定 Q=(4,3,2,1),高桥访问顶点 1,3,2,4 按此顺序并返回 R=(4,2,3,1)。不管怎样 Q Snuke 指定,不可能让 Takahashi 返回字典序大于的序列 (4,2,3,1),所以最终返回的序列是 (4,2,3,1).

对于第二个测试用例,可以证明不存在满足条件的树。