/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
1 から N までの整数を並べ替えた列 P_1, P_2, \dots, P_N が与えられます。 これを、最長増加部分列の長さが等しいような 2 つの部分列に分けることは可能でしょうか。
形式的に述べると、目標は以下の条件を全て満たす 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 から N までの整数を並べ替えた列である。
- 全テストケースにおける N の総和は 2 \cdot 10^5 以下である。
入力
入力は以下の形式で標準入力から与えられる。 入力の 1 行目は次の通りである。
T
そして、それぞれ以下の形式で T 個のテストケースが続く。
N P_1 P_2 \dots P_N
出力
各テストケースについて、与えられた並びを最長増加部分列の長さが等しいような 2 つの部分列に分けることが可能なら YES、そうでなければ NO と出力せよ。
1 行につき 1 個のテストケースへの出力を行え。
なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。
入力例 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] に分けると、両者とも最長増加部分列の長さが 2 となります。
[2, 3, 4, 5, 6, 1] については、最長増加部分列の長さが等しいような 2 つの部分列に分けることは不可能であることが示せます。
Score : 1000 points
Problem Statement
You are given a permutation P_1, P_2, \dots, P_N of integers from 1 to N. Is it possible to split it into 2 subsequences, which have equal length of the Longest Increasing Subsequence?
Formally speaking, your goal is to get two integer sequences a and b such that:
- Both a and b are subsequences of P.
- Each integer i=1,2,\cdots,N appears in exactly one of a and b.
- (The length of a longest increasing subsequence of a) = (The length of a longest increasing subsequence of b)
Determine if the objective is achievable.
You will be given T test cases. Solve each of them.
Constraints
- 1 \le T \le 2 \cdot 10^5
- 1 \le N \le 2 \cdot 10^5
- P_1, P_2, \dots, P_N is a permutation of integers from 1 to N.
- The sum of N over all test cases doesn't exceed 2 \cdot 10^5.
Input
Input is given from Standard Input in the following format. The first line of input is as follows:
T
Then, T test cases follow, each of which is in the following format:
N P_1 P_2 \dots P_N
Output
For each test case, print YES if it is possible to split the permutation into 2 subsequences, which have equal length of the Longest Increasing Subsequence, and print NO otherwise.
Use one line for each case.
Note that the checker is case-insensitive: you can print letters in both uppercase and lowercase.
Sample Input 1
5 1 1 2 2 1 3 1 2 3 5 1 3 5 2 4 6 2 3 4 5 6 1
Sample Output 1
NO YES NO YES NO
[1, 3, 5, 2, 4] can be split into [1, 5] and [3, 2, 4], both have LIS of length 2.
It can be shown that there is no way to split [2, 3, 4, 5, 6, 1] into 2 subsequences with an equal length of LIS.