← 返回题目列表

AtCoder · agc052_d

D. 等于 LIS

中文机器翻译题面 查看原题

分数: 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.