Cho một dãy gồm \(n\) số nguyên, bạn hãy lập trình tính toán độ dài của dãy con tăng dài nhất trong dãy đó (dãy con dài nhất mà mỗi phần tử đều lớn hơn phần tử liền trước nó).

Dãy con là một dãy có thể thu được từ dãy ban đầu bằng cách xóa bớt một số (có thể là không xóa) phần tử và giữ nguyên trật tự của các phần tử còn lại.

Input

Dòng đầu chứa số nguyên dương \(n\) - độ dài của dãy.

Dòng tiếp theo chứa \(n\) số nguyên \(x_1\), \(x_2\),..., \(x_n\) thể hiện các phần tử của dãy.

Output

Một số nguyên duy nhất là độ dài của dãy con tăng dài nhất.

Ví dụ

Input

8
7 3 5 3 6 2 9 8

Output

4

Ràng buộc

• \(1 \leq n \leq 2.10^5\).
• \(1 \leq x_i \leq 10^9\).