分数: 1000 点
问题陈述
给你一个排列 P_1, P_2, \dots, P_N 的整数来自 1 to N。 是否可以将其拆分为 2 子序列,其最长递增子序列的长度相等?
正式来说,你的目标是获得两个整数序列 a 和 b 这样:
- 两者 a 和 b 是子序列 P.
- 每个整数 i=1,2,\cdots,N 正好出现在以下之一中 a 和 b.
- (最长递增子序列的长度 a) = (最长递增子序列的长度 b)
确定目标是否可以实现。
你将得到 T 测试用例。解决它们中的每一个。
约束
- 1 \le T \le 2 \cdot 10^5
- 1 \le N \le 2 \cdot 10^5
- P_1, P_2, \dots, P_N 是来自以下整数的排列 1 to N.
- 总和 N 所有测试用例不超过 2 \cdot 10^5.
输入
输入由标准输入按以下格式给出。 第一行输入如下:
T
然后, T 测试用例如下,每个测试用例的格式如下:
N P_1 P_2 \dots P_N
输出
对于每个测试用例,打印 YES 如果可以将排列分成 2 子序列,其与最长递增子序列的长度相等,并打印 NO 否则。
每种情况使用一行。
请注意,检查器不区分大小写:您可以打印大写和小写字母。
示例输入 1
5 1 1 2 2 1 3 1 2 3 5 1 3 5 2 4 6 2 3 4 5 6 1
示例输出 1
NO YES NO YES NO
[1, 3, 5, 2, 4] 可以分为 [1, 5] 和 [3, 2, 4],两者都有 LIS 长度为 2。
可以证明,没有办法分割 [2, 3, 4, 5, 6, 1] 进入 2 长度相等的子序列 LIS.