Cho ~1~ dãy gồm ~n~ học sinh đang xếp hàng, học sinh đứng thứ ~i~ có chiều cao là ~H_i~. Do người thấp hơn mà ở sau người cao thì sẽ không thấy được gì, thầy giáo muốn tách các học sinh này ra sao cho vẫn giữ đúng thứ tự ban đầu. Đầu tiên, thầy muốn chọn ra các học sinh (không cần liên tiếp) có chiều cao tăng dần sao cho có nhiều học sinh nhất.

Input

Dòng đầu là số nguyên ~n~ (~n \le 1000~).

Dòng thứ ~2~ là dãy số nguyên ~H~ (~H_i \le 10^6, \forall i~).

Output

Ghi ra dãy học sinh có chiều cao tăng dần dài nhất.

Sample Input

6
4 2 4 8 5 7

Sample Output

4

Giải thích

Các học sinh ~2, 3, 5, 6~.