AT_agc052_d [AGC052D] Equal LIS

[problemUrl]: https://atcoder.jp/contests/agc052/tasks/agc052_d $ 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 $ 個のテストケースへの出力を行え。 なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。

### 制約 - $ 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 $ つの部分列に分けることは不可能であることが示せます。