最長増加部分列

数列 A = {a₀, a₁, … , a_n−1} の最長増加部分列 (LIS: Longest Increasing Subsequence) の長さを求めてください。 数列 A の増加部分列は 0 ≤ i₀ < i₁ < … < i_k < n かつ　a_i0 < a_i1 < … < a_ik を満たす部分列 {a_i0, a_i1, … , a_ik} です。最長増加部分列はその中で最も k　が大きいものです。

入力

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

出力

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

制約

• 1 ≤ n ≤ 100,000
• 0 ≤ a_i ≤ 10⁹

入出力例

入力例 1

5
5
1
3
2
4

出力例 1

3

入力例 2

3
1
1
1

出力例 2

1

Note

      解説      

---