配点 : $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$ 個のテストケースへの出力を行え。 なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。

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, 3, 5, 2, 4]$ を $[1, 5]$ と $[3, 2, 4]$ に分けると、両者とも最長増加部分列の長さが $2$ となります。

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