CFCF2171D.Rae Taylor and Trees (easy version)

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

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

—— 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”都被视为正确。

输入#1

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

输出#1

Yes
No
No
Yes
No
Yes
Yes
Yes
Yes

在第一个样例中，我们可以构造如下边集的树：

那么就有：

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