Bài toán: Tìm độ dài dãy con tăng dài nhất (LIS)

Đề bài

Cho một mảng gồm ~n~ số nguyên. Nhiệm vụ của bạn là tìm độ dài của dãy con tăng dài nhất trong mảng, tức là dãy con mà mọi phần tử đều tăng dần so với phần tử trước đó.

Dãy con là dãy được tạo ra từ mảng ban đầu bằng cách xóa đi một số phần tử (hoặc không xóa phần tử nào) mà không làm thay đổi thứ tự các phần tử còn lại.

Input

• Dòng đầu tiên chứa một 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

• In ra một số nguyên: độ dài của dãy con tăng 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:

• Dãy con tăng dài nhất là ~3, 5, 6, 9~, có độ dài là 4.