Tý tham gia cuộc thi xếp hình khối do trường tổ chức nhân dịp ngày 20/11. Ban tổ chức đưa cho mỗi bạn một dãy gồm \(N\) khối hình, mỗi khối có ghi một số nguyên. Người chơi được chọn ra một số khối và xếp chúng thành hàng ngang theo đúng thứ tự ban đầu của dãy, với điều kiện các số trên những khối được chọn phải tăng dần (khối sau phải có số ghi lớn hơn khối trước). Bạn nào chọn được nhiều khối nhất sẽ giành giải.

Tý rất muốn thắng nên nhờ bạn tính trước xem với dãy đã cho, có thể chọn được dãy con tăng dần dài tối đa bao nhiêu khối.

Định dạng đầu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(1 \le N \le 2 \times 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).

Định dạng đầu ra

• In ra số khối lớn nhất có thể chọn, tức là độ dài dãy con tăng dần dài nhất.

Ví dụ

Input:

8
2 5 3 7 11 8 10 13

Output:

6

Ràng buộc

• \(20\%\) số điểm ứng với \(N \le 20\).
• \(30\%\) số điểm ứng với \(N \le 2000\).
• \(50\%\) số điểm còn lại không có ràng buộc gì thêm.