← 返回题目列表

AtCoder · tessoku_book_x

A24. 最长递增子序列

中文机器翻译题面 查看原题

配点: 1000 点

問題文

配列 A = [A_1, A_2, \cdots, A_N] 的最长递增子序列的长度。

制約

  • 1 \leq N \leq 100000
  • 1 \leq A_i \leq 500000
  • 所有输入均为整数

入力

输入是按以下格式从标准输入给出的。

N
A_1 A_2 \cdots A_N

出力

请将答案输出为整数。


入力例 1

6
2 3 1 6 4 5

出力例 1

4

列 [2, 3, 4, 5] 是最长的递增子序列。


入力例 2

10
1 1 1 1 1 1 1 1 1 1

出力例 2

1