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 翻译