Cho một dãy số nguyên gồm ~N~ phần tử ~X_1, X_2, ..., X_N~.

Biết rằng dãy con tăng đơn điệu là dãy ~X_{i_1}, X_{i_2}, ..., X_{i_k}~ thỏa mãn điều kiện ~i_1 < i_2 < ... < i_k~ và ~X_{i_1} < X_{i_2} < ... < X_{i_k}~. Hãy cho biết dãy con tăng đơn điệu dài nhất có bao nhiêu phần tử?

Input

• Dòng đầu tiên gồm 1 số nguyên dương ~N (1 \leq N \leq 1000)~
• Dòng thứ 2 gồm ~N~ số nguyên ~X_1, X_2, ..., X_N (1 \leq X_i \leq 10000)~

Output

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

Sample input

5
1 3 2 6 8

Sample output

4

Note

Dãy con tăng đơn điệu dài nhất là dãy ~X_1 = 1 < X_2 = 3 < X_4 = 6 < X_5 = 8~, độ dài dãy này bằng 4