题目描述

$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$ 行目は次の通りである。

$T$

そして、それぞれ以下の形式で $T$ 個のテストケースが続く。

$N$ $P_1$ $P_2$ $\dots$ $P_N$

输出格式

各テストケースについて、与えられた並びを最長増加部分列の長さが等しいような $2$ つの部分列に分けることが可能なら YES、そうでなければ NO と出力せよ。 $1$ 行につき $1$ 個のテストケースへの出力を行え。 なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。

题目大意

给定长度为 $n$ 的排列 $p$，判断是否能将其分成两个子序列使得它们的 LIS 相同，不需要构造方案。

多测。$\sum n\le 2\times 10^5$。

5
1
1
2
2 1
3
1 2 3
5
1 3 5 2 4
6
2 3 4 5 6 1

NO
YES
NO
YES
NO

提示

制約

• $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$ 以下である。

Sample Explanation 1

$[1,\ 3,\ 5,\ 2,\ 4]$ を $[1,\ 5]$ と $[3,\ 2,\ 4]$ に分けると、両者とも最長増加部分列の長さが $2$ となります。 $[2,\ 3,\ 4,\ 5,\ 6,\ 1]$ については、最長増加部分列の長さが等しいような $2$ つの部分列に分けることは不可能であることが示せます。