問題文

配列 A = [A_1, A_2, \cdots, A_N] の最長増加部分列の長さを求めてください。

制約

• 1 \leq N \leq 100000
• 1 \leq A_i \leq 500000
• 入力はすべて整数

入力例 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