← 返回题目列表

Codeforces · 2171/D

D. 雷·泰勒和树木(简单版)

中文机器翻译题面 查看原题
“没想到一个平民竟然能理解坐在我旁边。知道你的位置!”
— 克莱尔·弗朗索瓦

这是问题的简单版本。简单版本和困难版本之间的唯一区别在于,困难版本要求您构建一个令人满意的树的示例。

作为一名土系法师,雷伊已经掌握了种植树木的咒语!但马纳里亚吹嘘说她可以种植更令人印象深刻的树种。雷记得最稀有的树可以使用某种排列所代表的公式来种植——请帮助她构建它!

给你一个长度为 $$$n$$$ 的排列$$$^{\text{∗}}$$$ $$$p$$$。

判断是否存在一棵无向树,其$$$n$$$个顶点标记为$$$1, 2, \dots, n$$$,满足以下条件:

  • 令 $$$u$$$ 和 $$$v$$$ ($$$1\leq {\color{red}{u \lt v}} \leq n$$$) 为由边连接的任意两个顶点。那么$$$u$$$ 出现在$$$p$$$ 中的$$$v$$$ 之前。

$$$^{\text{*}}$$$长度 $$$n$$$ 的排列是一个数组,其中包含从 $$$1$$$ 到 $$$n$$$ 的每个整数,且顺序任意。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — 测试用例的数量。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2\leq n\leq 2\cdot 10^5$$$)。

每个测试用例的第二行包含 $$$n$$$ 整数,$$$p_1, p_2, \dots, p_n$$$ ($$$1\leq p_i\leq n$$$)。保证所有 $$$p_i$$$ 都是不同的。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,在单行上输出“是“如果存在满足给定条件的树,并且”No”否则。

您可以在任何情况下输出答案(上限或下限)。例如,字符串“是", "是的", "是“,和”是的“将被识别为”是".

示例

输入
复制

9
6
1 3 4 5 2 6
4
3 4 1 2
5
4 3 5 1 2
4
1 2 3 4
7
4 3 5 7 6 2 1
6
2 4 6 1 3 5
3
2 1 3
4
2 4 1 3
6
4 2 6 5 1 3

输出
复制

Yes
No
No
Yes
No
Yes
Yes
Yes
Yes

注意

在第一个示例中,我们可以构造具有以下边的树:

  • $$$\{3, 1\}$$$,
  • $$$\{4, 1\}$$$,
  • $$$\{6, 5\}$$$,
  • $$$\{6, 2\}$$$,
  • $$$\{6, 1\}$$$.

然后我们就有了

  • $$$1 \lt 3$$$,且 $$$1$$$ 出现在 $$$p$$$ 中的 $$$3$$$ 之前,
  • $$$1 \lt 4$$$,且 $$$1$$$ 出现在 $$$p$$$ 中的 $$$4$$$ 之前,
  • $$$5 \lt 6$$$,并且 $$$5$$$ 出现在 $$$p$$$ 中的 $$$6$$$ 之前,
  • $$$2 \lt 6$$$,且 $$$2$$$ 出现在 $$$p$$$ 中的 $$$6$$$ 之前,
  • $$$1 \lt 6$$$,并且 $$$1$$$ 出现在 $$$p$$$ 中的 $$$6$$$ 之前。

在第二个示例中,可以证明不存在满足给定约束的树。