Cho dãy số nguyên gồm ~N~ phần tử ~A_1, A_2, ..., A_N~

Biết rằng dãy con tăng đơn điệu là 1 dãy ~A_{i_1}, ..., A_{i_k}~ thỏa ~i_1 < i_2 < ... < i_k~ và ~A_{i_1} < A_{i_2} ... < A_{i_k}~

Yêu cầu

Hãy cho biết dãy con tăng đơn điệu dài nhất của dãy này có bao nhiêu phân tử

Input

• Dòng 1 gồm 1 số nguyên ~N~ ~(1 \le N \le 1000)~
• Dòng thứ 2 ghi ~N~ số nguyên ~A_1, A_2, ..., A_N (1 \le A_i \le 10000)~

Output

• Ghi ra độ dài dãy con tăng dài nhất

Scoring

• không có ràng buộc gì thêm

Ví dụ

Input

6
1 2 5 4 6 2

Output

4