AT_arc211_e.[ARC211E] Greedy Takahashi 2

给定一个正整数 $N$ 和一个排列 $P$，其中 $P$ 是 $1,2,\dots,N$ 的一个排列。

现在有一棵有 $N$ 个点的树，这些点编号为 $1,2,\dots,N$。Snuke 和 Takahashi 根据以下规则行动：

• Snuke 会指定一个 $1,2,\dots,N$ 的排列 $Q$，使得 Takahashi 按下述规则操作后返回的序列，是在所有可能情况下字典序最大的。
• Takahashi 初始在树的 $1$ 号节点，他先获得 $Q$，然后将序列 $R$ 初始化为长度为 $1$ 的序列 $(Q_1)$。他接下来进行 $N-1$ 次如下操作，最终返回 $R$：
  • 在所有与之前已访问节点相连且尚未访问的节点中，访问 $Q_i$ 最小的那个节点 $i$，然后把 $Q_i$ 加到 $R$ 末尾。

这里，节点 $1$ 被认为最开始已经访问过。

你的任务是判断，是否存在某棵树，使得 Takahashi 最终返回的序列为 $P$。

你将获得 $T$ 个测试用例，每个都需要分别判断。

输入由标准输入给出，格式如下：

$T$
第 1 个测试用例
第 2 个测试用例
$\vdots$
第 $T$ 个测试用例

每个测试用例格式如下：

$N$ $P_1$ $P_2$ $\ldots$ $P_N$

输出 $T$ 行。

第 $i$ 行应为 Yes，表示第 $i$ 个测试用例存在满足条件的树；否则输出 No。

样例解释 1

对于第一个测试用例，存在一棵 $4$ 个点的树 $1-2$，$1-3$，$2-4$，它满足条件。

Snuke 若选择 $Q=(4,3,2,1)$，Takahashi 会按顺序访问 $1,3,2,4$ 号点，并返回 $R=(4,2,3,1)$。无论 Snuke 选择什么 $Q$，Takahashi 最终返回的序列字典序不会超过 $(4,2,3,1)$，所以最终返回的就是 $(4,2,3,1)$。

对于第二个测试用例，可以证明不存在满足条件的树。

数据范围

• $1 \le T \le 10^5$
• $1 \le N \le 2 \times 10^5$
• $P$ 是 $1,2,\dots,N$ 的一个排列
• 所有测试用例中的 $N$ 之和不超过 $2 \times 10^5$
• 所有输入均为整数

由 ChatGPT 5 翻译