問題一覧 > 通常問題

No.1827 最長部分スーパーリッチ門松列列

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 50
作問者 : maimai / テスター : 37zigen37zigen
7 ProblemId : 6027 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-26 01:10:12

定義

本問題では、以下を満たす長さ2以上の数列 $a_1 \ldots a_n$ をスーパーリッチ門松列列と呼ぶことにします。

  • 数列の要素は全て異なる
  • $\min_{i\in \text{偶数}}a_i \gt \max_{i\in\text{奇数}}a_i$ または $\max_{i\in\text{偶数}}a_i \lt \min_{i\in\text{奇数}}a_i$

定義のオリジナルはNo.122 傾向と対策:門松列(その3)ですが、 任意の長さの数列に拡張されている点に注意してください。
また、本定義は門松列列とは異なります。$1,3,2,5,4$ は門松列列の条件を満たしますが、スーパーリッチ門松列列の条件を満たしません。

問題文

順列 $P_1\ldots P_N$ のスーパーリッチ門松列列を満たす部分列(連続しなくても良い)のうち、最長のものの長さを出力してください。

入力

$T$ 個のテストケースが同時に与えられます。$(1 \le T \le 10^5)$

$T$
$\text{TestCase}_1$
$\vdots$
$\text{TestCase}_T$

各テストケースは以下のフォーマットに従って与えられます。

$N$
$P_1$ $\ldots$ $P_N$
  • $3 \le N \le 5\times 10^5$
  • $1 \le P_i \le N$
  • $P_i \neq P_j , (i \neq j)$

複数のテストケースが存在する時、$N$ の総和は $5\times 10^5$ を超えません。

出力

各テストケースごとに、解となる値を改行区切りで出力してください。

サンプル

サンプル1
入力
3
5
1 4 3 2 5
5
2 1 3 5 4
6
1 2 3 4 5 6
出力
4
3
2

1つ目のテストケースは、1 4 3 2 5が与えられています。
例えば、1 4 2 5 は入力の部分列であり、かつスーパーリッチ門松列列を満たします。
1 4 3 2 5 は入力の部分列ですが、スーパーリッチ門松列列を満たしません。
長さ4が最長なので、4を出力します

$2,1,5,4$ は門松列列の条件を満たしますが、スーパーリッチ門松列列の条件を満たしません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。