AT_agc052_d [AGC052D] Equal LIS

给定一个 $1$ 到 $N$ 的整数的排列 $P_1,\ P_2,\ \dots,\ P_N$。请判断是否可以将其分成两个子序列，使得这两个子序列的最长上升子序列的长度相等。 形式化地说，目标是找到满足以下所有条件的两个整数序列 $a,\ b$： - $a,\ b$ 都是 $P$ 的子序列。 - 每个整数 $i=1,2,\cdots,N$ 恰好只在 $a$ 或 $b$ 中出现一次。 - （$a$ 的最长上升子序列的长度）$=$（$b$ 的最长上升子序列的长度）。 请判断目标是否可以达成。 有 $T$ 组测试数据，请分别作答。

输入从标准输入读入。输入的第 $1$ 行为： > $T$ 接下来有 $T$ 组测试数据，每组数据格式如下： > $N$ $P_1$ $P_2$ $…$ $P_N$

对于每组测试数据，如果可以将给定排列分成两个最长上升子序列长度相等的子序列，则输出 `YES`，否则输出 `NO`。每组测试输出占一行。判题器对大小写不敏感。

### 数据范围 - $1\leq T\leq 2\times 10^5$ - $1\leq N\leq 2\times 10^5$ - $P_1,\ P_2,\ \dots,\ P_N$ 是 $1$ 到 $N$ 的一个排列。 - 所有测试数据中 $N$ 的总和不超过 $2\times 10^5$。 ### 样例解释 1 将 $[1,\ 3,\ 5,\ 2,\ 4]$ 分为 $[1,\ 5]$ 和 $[3,\ 2,\ 4]$，两者的最长上升子序列长度均为 $2$。对于 $[2,\ 3,\ 4,\ 5,\ 6,\ 1]$，无法分成两个最长上升子序列长度相等的子序列。 由 ChatGPT 4.1 翻译