Dãy con tăng dài nhất 2(LIS).

Bạn được cung cấp một mảng chứa n số nguyên. Nhiệm vụ của bạn là xác định dãy con dài nhất tăng dần trong mảng, tức là dãy con dài nhất mà mọi phần tử đều lớn hơn phần tử trước đó. Một dãy con là một dãy có thể được dẫn xuất từ mảng bằng cách xóa một số phần tử mà không làm 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. Sau đó có n số nguyên x1, x2,…, xn: nội dung của mảng. (1≤n≤2⋅10^5; 1≤xi≤10^9)

Constraints

.

Output Format

In ra chiều dài của dãy con tăng dài nhất.

Ví dụ:

Dữ liệu vào

6
1 2 4 1 5 2

Dữ liệu ra

4