Xây Tháp Khối Vuông (Dạng LIS)

Phát biểu bài toán: Bé An có N khối vuông, được đánh số từ 1 đến N. Các khối vuông được xếp thành một hàng ngang. Khối thứ i có trọng lượng là W[i]. An muốn xây một cái tháp bằng cách xếp chồng các khối vuông lên nhau theo một quy tắc duy nhất: một khối vuông chỉ có thể được đặt lên trên một khối vuông khác nếu nó có trọng lượng lớn hơn hẳn.
An sẽ chọn các khối vuông từ hàng ngang (không nhất thiết phải liền kề nhau) để xây tháp. Hãy giúp An tìm ra chiều cao lớn nhất (số khối vuông nhiều nhất) của cái tháp mà cậu bé có thể xây được.

Input:
• Dòng đầu tiên chứa số nguyên N (1 ≤ N ≤ 1000).
• Dòng thứ hai chứa N số nguyên W[1], W[2], ..., W[N] (1 ≤ W[i] ≤ 1.000.000), là trọng lượng của các khối vuông.
Output:
• Một số nguyên duy nhất là chiều cao tối đa của cái tháp.

Ví dụ:
Input:
8
5 2 8 6 3 6 9 7
Output:
4

Giải thích:
An có thể chọn các khối vuông có trọng lượng {2, 3, 6, 9} hoặc {2, 3, 6, 7} để xây một cái tháp cao 4 tầng.