← 返回题目

题库练习 Rae Taylor and Trees (easy version)

← 上一题下一题 →

A16551 | $Rae Taylor and Trees (easy version)$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

C++ 编辑器

输入

输出