题目描述

“居然有平民敢妄想坐在我身边。要认清自己的位置！”

—— Claire François

这是此题的简单版本。简单版与困难版唯一的区别在于：困难版要求你构造出满足条件的树的一个例子。

作为大地的魔法师，Rae 已掌握种植树木的法术！但 Manaria 吹嘘她能种出更加稀有的树种。Rae 记得，最稀有的树木类型可以用一个特定的排列公式来生长——请你帮她构造出来！

给定一个长度为 $n$ 的排列 $p$。

判断是否存在一棵无向树，该树有 $n$ 个顶点，编号为 $1,2,\dots,n$，满足下列条件：

• 对于任意一条边 $(u,v)$（$1 \leq u < v \leq n$），如果顶点 $u$ 和顶点 $v$ 之间有边，则 $u$ 在 $p$ 中出现的位置必须在 $v$ 之前。

$^*$排列指的是长度为 $n$ 的、由 $1$ 到 $n$ 的所有正整数组成且不重复的数组。

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$2 \leq n \leq 2 \times 10^5$）。

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

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

输出格式

对于每个测试用例，输出一行。如果存在满足条件的树，输出 “Yes”；否则输出 “No”。

你可以以任意大小写输出答案。例如，“yEs”、“yes”、“YES”、“yeS”都被视为正确。

样例

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 < 3$，并且 $1$ 在 $p$ 中出现在 $3$ 之前，
• $1 < 4$，并且 $1$ 在 $p$ 中出现在 $4$ 之前，
• $5 < 6$，并且 $5$ 在 $p$ 中出现在 $6$ 之前，
• $2 < 6$，并且 $2$ 在 $p$ 中出现在 $6$ 之前，
• $1 < 6$，并且 $1$ 在 $p$ 中出现在 $6$ 之前。

在第二个样例中，可以证明不存在一棵满足题目约束的树。

由 ChatGPT 5 翻译

来源

Codeforces 2171D，英文题名 Rae Taylor and Trees (easy version)。