“没想到一个平民竟然能理解坐在我旁边。知道你的位置!”
— 克莱尔·弗朗索瓦
这是问题的简单版本。简单版本和困难版本之间的唯一区别在于,困难版本要求您构建一个令人满意的树的示例。
作为一名土系法师,雷伊已经掌握了种植树木的咒语!但马纳里亚吹嘘说她可以种植更令人印象深刻的树种。雷记得最稀有的树可以使用某种排列所代表的公式来种植——请帮助她构建它!
给你一个长度为 $$$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”否则。
您可以在任何情况下输出答案(上限或下限)。例如,字符串“是", "是的", "是“,和”是的“将被识别为”是".
示例
输入复制
961 3 4 5 2 643 4 1 254 3 5 1 241 2 3 474 3 5 7 6 2 162 4 6 1 3 532 1 342 4 1 364 2 6 5 1 3
输出复制
YesNoNoYesNoYesYesYesYes
注意
在第一个示例中,我们可以构造具有以下边的树:
- $$$\{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$$$ 之前。
在第二个示例中,可以证明不存在满足给定约束的树。