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