Những Mốc Tăng Dần

Cho một dãy gồm $n$ số nguyên. Bạn được chọn một số phần tử, không nhất thiết nằm cạnh nhau, nhưng phải giữ nguyên thứ tự xuất hiện của chúng trong dãy ban đầu. Hãy tìm số phần tử lớn nhất có thể chọn sao cho mỗi giá trị được chọn sau đều lớn hơn nghiêm ngặt giá trị đứng trước nó.

Input

• Dòng đầu chứa số nguyên $n$.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.

Output

• In một số nguyên: độ dài lớn nhất của một dãy con tăng nghiêm ngặt.

Constraints

• $1\le n\le 2\cdot 10^5$.
• $1\le a_i\le 10^9$ với mọi $1\le i\le n$.
• Đáp án là một số nguyên trong đoạn từ $1$ đến $n$.
• Các vị trí được chọn phải tăng dần, còn các giá trị tương ứng phải tăng nghiêm ngặt; hai giá trị bằng nhau không thể đứng liên tiếp trong dãy được chọn.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 2000$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

8
5 1 4 2 3 9 6 7

5