Dãy con tăng dài nhất (Increasing Subsequence)

Nguồn: CSES

Phiên bản: Phước Hưng OJ Extended

Đề bài

Cho dãy $n$ số nguyên $x_1,x_2,\ldots,x_n$.

Một dãy con được tạo bằng cách xóa một số phần tử nhưng giữ nguyên thứ tự tương đối của các phần tử còn lại.

Hãy tìm độ dài lớn nhất của một dãy con tăng nghiêm ngặt, tức mỗi phần tử sau phải lớn hơn phần tử trước.

Input

Dòng đầu chứa $n$.

Dòng thứ hai chứa $n$ số nguyên.

Output

In độ dài dãy con tăng nghiêm ngặt dài nhất.

Subtask

• Subtask 1 — 20%: $n\le2000$.
• Subtask 2 — 30%: $n\le50000$.
• Subtask 3 — 50%: $1\le n\le2\cdot10^5$, $1\le x_i\le10^9$.

Ví dụ

Input

8
7 3 5 3 6 2 9 8

Output

4

Giải thích

Một dãy con tăng dài nhất là $3,5,6,9$ hoặc $3,5,6,8$, có độ dài $4$.