Cho dãy n số nguyên. Hãy tìm độ dài dãy con tăng thực sự dài nhất (các phần tử được chọn giữ nguyên thứ tự trong dãy ban đầu nhưng không cần liên tiếp).
Minh họa dãy con tăng
Dữ liệu vào
Dòng đầu chứa n. Dòng thứ hai chứa n số nguyên.
Kết quả
Độ dài dãy con tăng dài nhất.
Giới hạn
1 ≤ n ≤ 10^5; |ai| ≤ 10^9.
Ví dụ 1 – vào
8 10 9 2 5 3 7 101 18
Ví dụ 1 – ra
4
Ví dụ 2 – vào
3 5 5 5
Ví dụ 2 – ra
1