F - Double-Ended Purge Sort
Ceylon
2
s
1024
MB
550
点
問題文
非負整数列 $A=(A_1, A_2, A_3, \ldots, A_N)$ が与えられます。
$i=1,2,3,\ldots,N$ の順に、数列 $S$ に以下のいずれか $1$ つの操作を行います。はじめ、 $S=()$ です。
- $A_i$ を $S$ の先頭に追加する。
- $A_i$ を $S$ の末尾に追加する。
- 何もしない。
操作をすべて終えた後の $S$ としてありうる広義単調増加な数列のうち、最長のものの長さを求めてください。
制約
すべてのテストケースについて、以下の制約を満たす。
- 入力はすべて整数
- $1\leq N\leq 2\times 10^5$
- $0\leq A_i\leq 10^{18}\ (1\leq i\leq N)$
部分点
この問題には、部分点が設定されている。部分点の採点方法については、コンテストトップ を参照すること。
- ($150$ 点)
- $N \leq 14$
- ($150$ 点)
- $N \leq 400$
- ($250$ 点)
- 追加の制約はない。
入力
入力は以下の形式で標準入力から与えられる。
$N$
$A_1$ $A_2$ $\ldots$ $A_N$
出力
答えを出力せよ。
入力例 1
4
4 1 2 3
出力例 1
3
順に以下のような操作を行うことで、 $S=(1,2,3)$ とすることができます。
- $A_1=4$ である。何もしない。 $S=()$ となる。
- $A_2=1$ である。 $A_2$ を $S$ の先頭に追加する。 $S=(1)$ となる。
- $A_3=2$ である。 $A_3$ を $S$ の末尾に追加する。 $S=(1,2)$ となる。
- $A_4=3$ である。 $A_4$ を $S$ の末尾に追加する。 $S=(1,2,3)$ となる。
どのように操作を行ったとしても、 $S$ を長さが $4$ 以上の広義単調増加な数列にすることはできないため、 $3$ を出力します。
この入力は、部分点 1., 2. の制約を満たします。
入力例 2
4
4 3 2 1
出力例 2
4
順に以下のような操作を行うことで、 $S=(1,2,3,4)$ とすることができます。
- $A_1=4$ である。 $A_1$ を $S$ の末尾に追加する。 $S=(4)$ となる。
- $A_2=3$ である。 $A_2$ を $S$ の先頭に追加する。 $S=(3,4)$ となる。
- $A_3=2$ である。 $A_3$ を $S$ の先頭に追加する。 $S=(2,3,4)$ となる。
- $A_4=1$ である。 $A_4$ を $S$ の先頭に追加する。 $S=(1,2,3,4)$ となる。
よって、 $4$ を出力します。
この入力は、部分点 1., 2. の制約を満たします。
入力例 3
10
5000000000000000 700000000000000000 60000000000000000 60000000000000000 700000000000000000 400000000000000 60000000000000000 700000000000000000 5000000000000000 5000000000000000
出力例 3
8
入力が 32bit 整数型の範囲に収まらない場合に注意してください。
この入力は、部分点 1., 2. の制約を満たします。