Dãy con tăng dài nhất (N nhỏ)

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 5000\)
• \(|A_i| \le 10^9\)

Sample Input

7
4 -2 7 7 0 9 3

Sample Output

3

Explanation

Một dãy con tăng dài nhất là \(4, 7, 9\) (hoặc \(-2, 0, 9\) ...). Không có dãy tăng nào có \(4\) phần tử.