Độ dài tối đa của chuỗi con tăng dần

Trong một buổi thảo luận về vật lý học, FullHouse Dev đã được giao một nhiệm vụ thú vị liên quan đến các dãy số. Họ cần tìm ra cách xác định độ dài của chuỗi con tăng dần dài nhất trong một mảng số nguyên. Với sự quyết tâm, FullHouse Dev đã bắt đầu phân tích và giải quyết vấn đề này.

Bài toán

FullHouse Dev nhận được một mảng \(A\) chứa \(n\) số nguyên. Nhiệm vụ của nhóm là tìm ra độ dài của chuỗi con tăng dần dài nhất trong mảng \(A\). Một chuỗi con là một chuỗi có thể được tạo ra từ mảng bằng cách xóa một số phần tử mà không thay đổi thứ tự của các phần tử còn lại.

INPUT FORMAT:

• Dòng đầu tiên chứa số nguyên \(n\): kích thước của mảng.
• Dòng tiếp theo chứa \(n\) số nguyên \(x_1, x_2, \ldots, x_n\): các phần tử của mảng.

OUTPUT FORMAT:

• In ra độ dài của chuỗi con tăng dần dài nhất.

Ràng buộc:

• \(1 \leq n \leq 2 \cdot 10^5\)
• \(1 \leq x_i \leq 10^9\)

Ví dụ

INPUT

8
7 3 5 3 6 2 9 8

OUTPUT

4

Giải thích

• Trong ví dụ trên, chuỗi con tăng dần dài nhất là \(3, 5, 6, 9\) với độ dài là 4.