Độ dài dãy tăng

Bối cảnh và bài toán

Từ dãy số đo, bạn cần giữ lại một số vị trí theo đúng thứ tự sao cho giá trị tăng nghiêm ngặt.

Yêu cầu

Tính số phần tử lớn nhất có thể giữ lại.

Input

Dòng 1: n. Dòng 2: dãy a.

Output

In độ dài lớn nhất.

Ràng buộc

• 1 <= n <= 5000
• -10^9 <= a_i <= 10^9

Chấm điểm

Ví dụ 1

Input

8
7 3 5 3 6 2 9 8

Output

4

Giải thích. Ví dụ nhỏ giúp kiểm tra cách mô hình hóa trạng thái và kết quả cuối; khi tự giải, cần suy luận từ ràng buộc thay vì suy đoán từ sample.

Ví dụ 2

Input

5
5 4 3 2 1

Output

1

Giải thích. Hãy đối chiếu với edge case: trạng thái đầu, trạng thái không đạt được, tie hoặc biên chỉ số tùy bài.

Thông tin bài tập

Nguồn: Phỏng theo / Adapted from CSES Increasing Subsequence. Bản FULLHOUSE DEV đã biên tập bối cảnh/format và ràng buộc khi cần để khớp scope-lock của khóa học.