Dãy con tăng dài nhất (N lớn)

Cho dãy gồm \(N\) số nguyên \(A_1, A_2, \dots, A_N\). Hãy tìm độ dài lớn nhất của một dãy con tăng nghiêm ngặt, tức là chọn các chỉ số \(i_1 < i_2 < \dots < i_k\) sao cho \(A_{i_1} < A_{i_2} < \dots < A_{i_k}\) và \(k\) lớn nhất.

Input

• Dòng thứ nhất chứa số nguyên \(N\).
• Dòng thứ hai chứa \(N\) số nguyên \(A_1, \dots, A_N\).

Output

In ra một số nguyên là độ dài dãy con tăng dài nhất.

Constraints

• \(1 \le N \le 2 \cdot 10^5\)
• \(|A_i| \le 10^9\)

Sample Input

7
8 3 -5 3 6 4 10

Sample Output

4

Explanation

Dãy \(-5, 3, 6, 10\) là một dãy con tăng có \(4\) phần tử; không có dãy tăng nào dài hơn.