Cho một mảng \(A\) gồm \(n\) phần tử, tìm dãy con tăng dài nhất \((LIS)\) của dãy \(A\).

Nói cách khác, tìm \(k\) lớn nhất sao cho tồn tại \(k\) chỉ số \(i_1 \lt i_2 \lt … \lt i_k\) mà \(A_{i_1} \lt A_{i_2} \lt… \lt A_{i_k}\).

Input

• Dòng đầu tiên gồm số nguyên \(n\).
• Dòng thứ hai gồm \(n\) số nguyên \(A_i\).

Output

• In ra độ dài \((LIS)\).

Điều kiện

• \(1 \le n \le 10^{3}\)
• \(1 \le A_{i} \le 10^{9}\)

Sample Input 1

5
3 7 2 1 8

Sample Output 1

3