Câu 2. (100 điểm) CỒN NỔI
Cồn Nổi là một đảo thuộc vùng biển huyện Kim Sơn, tỉnh Ninh Bình. Nơi đây đang được đầu tư xây dựng và hứa hẹn trở thành một điểm du lịch, nghỉ dưỡng hấp dẫn.
Trong một lần đến thăm Cồn Nổi, Nam đi dạo dọc bờ biển và nhặt được những vỏ ốc có kích thước tương ứng là các số a1, a2,…, an. Nam muốn lựa chọn một số vỏ ốc để xâu lại thành một chuỗi, sao cho khi tính từ đầu chuỗi đến cuối chuỗi các vỏ ốc phía sau có kích thước lớn hơn vỏ ốc phía trước.
Yêu cầu: Hãy tìm số vỏ ốc nhiều nhất mà Nam có thể chọn được.
Dữ liệu vào: File CNOI.INP gồm 2 dòng:
- Dòng đầu là số nguyên dương n (n <= 106).
- Dòng thứ hai ghi dãy các số nguyên dương a1, a2,…, an (ai <= 109), mỗi số cách nhau 1 khoảng trắng.
Dữ liệu ra: File CNOI.OUT ghi số vỏ ốc nhiều nhất mà Nam có thể xâu được thành chuỗi.
Ví dụ:
|
CNOI.INP |
CNOI.OUT |
|
6 6 5 8 8 3 6 |
4 |
|
8 6 1 2 2 7 6 2 5 |
5 |
Giới hạn dữ liệu: Trong bộ test của bài sẽ có:
+ 60% test với 0< n, ai <=103;
+ 20% test với 103<n, ai <= 105;