問題一覧 > 通常問題

No.1438 Broken Drawers

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 134
作問者 : ir_1st_vilir_1st_vil / テスター : 👑 maspymaspy
4 ProblemId : 4726 / 出題時の順位表
問題文最終更新日: 2021-03-20 23:45:06

問題文

Vil 君の家には壊れたタンスがあります。このタンスはどの段も一度引き出した後は引っ込めることができないため、 引き出した段の一つ下の段から物を取り出すことが出来なくなります(引き出した段が最下段である場合はこの限りではありません)。

タンスは下から順に番号の付いた合計 $N$ 段からなり、$i$ 段目の引き出しには整数 $A_i$ が入っています( $A_i$ はすべて異なる)。 このタンスの $B_1,B_2,\dots,B_M$ 段目からこの順に整数を取り出し、それらを取り出した順に並べることで長さ $M$ の単調増加列を作ることを考えます。 このとき、以下の条件を満たす必要があります。

  • 問題文中の $B$ について $B_i-1=B_j$ を満たす $(i,j)(i < j)$ は存在しない。

以上の条件を満たす単調増加列のうち最長のものの長さを求めてください。

入力

$N$
$A_1\ A_2\ \dots\ A_N$

  • 入力はすべて整数
  • $1 \le N \le 2 \times 10^5$
  • $1 \le A_i \le N$
  • $i \neq j$ であれば $A_i \neq A_j$

出力

問題文中の条件を満たす単調増加列のうち最長のものの長さを出力し、最後に改行してください。

サンプル

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

条件を満たす最長の単調増加列は $(1,2,3,5),(2,3,4,5)$ の $2$ 通りあります。

$(1,2,3,4,5)$ を作ることは出来ません。なぜならこの単調増加列について問題文中の $B$ を定義すると、 $B_1-1=4-1=3=B_4$ となり条件を満たしていないからです。

サンプル2
入力
8
4 3 5 1 7 6 2 8
出力
5
サンプル3
入力
15
12 5 15 3 11 8 14 13 6 10 9 7 4 2 1
出力
8

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