Combinatorial - Longest Increasing Subsequence

時間制限 : 1 sec, メモリ制限 : 65536 KB
英語版はこちら

最長増加部分列

数列 A = {a0, a1, … , an−1} の最長増加部分列 (LIS: Longest Increasing Subsequence) の長さを求めてください。 数列 A の増加部分列は 0 ≤ i0 < i1 < … < ik < n かつ ai0 < ai1 < … < aik を満たす部分列 {ai0, ai1, … , aik} です。最長増加部分列はその中で最も k が大きいものです。

入力

1行目に数列 A の長さを示す整数 n が与えられます。続く n 行で数列の各要素 ai が与えられます。

出力

最長増加部分列の長さを1行に出力してください。

制約

  • 1 ≤ n ≤ 100,000
  • 0 ≤ ai ≤ 109

入出力例


入力例 1

5
5
1
3
2
4

出力例 1

3

入力例 2

3
1
1
1

出力例 2

1

Note

      解説