CF2171D Rae Taylor and Trees (easy version)

“居然有平民敢妄想坐在我身边。要认清自己的位置！” —— 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”都被视为正确。

在第一个样例中，我们可以构造如下边集的树： - $\{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 翻译