Cho dãy số nguyên \(a_1,a_2,...a_n\) một dãy con \(a_{i_1},a_{i_2}...a_{i_m}\) không nhất thiết phải liên tục nhưng thứ tự phải được giữ nguyên đảm bảo phần tử nào đứng trước trong dãy ban đầu thì cũng phải đứng trước trong dãy con và thỏa mãn tính chất đơn điệu tăng ngặt.

Bài toán đặt ra là có rất nhiều dãy con đơn điệu tăng ngặt như vậy ngay cả khi các dãy con đơn điệu tăng ngặt có độ dài dài nhất cũng có thể có nhiều. Hãy tìm độ dài của dãy con đơn điệu tăng dài nhất của dãy đã cho ban đầu

Input

Dòng 1 chứa số nguyên dương n \((1<=n<=4000)\)

Dòng 2 chứa các phần tử của dãy là các số nguyên dương có giá trị tuyệt đối không quá \(10^4\)

Output

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

Ví dụ

Input

10
4 7 3 5 8 2 9 1 6 3

Output

4

Giải thích : Có nhiều dãy con đơn điệu tăng độ dài dài nhất là 4 gồm \(\{4,7,8,9\}\) hoặc \(\{3,5,8,9\}\) hoặc \(\{4,5,8,9\} ...\)

Chú ý: Đây là bài dễ còn bài khó hơn xem tại Lại là dãy con đơn điệu tăng dài nhất