Cho một dãy số nguyên gồm \(N\) phần tử \(A_1, A_2, \dots,A_N\).

Biết rằng dãy con tăng đơn điệu là \(1\) dãy \(A_{i_{1}}, \dots, A_{i_{k}}\) thỏa mãn \(i_{1} < i_{2} < \dots < i_{k}\) và \(A_{i_{1}} < A_{i_{2}} < \dots < A_{i_{k}}\). 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 là số \(N (1 \le N \le 1000)\).
• Dòng thứ \(2\) ghi \(N\) số nguyên \(A_1, A_2, \dots, A_N (1 \le A_i \le 10000)\).

Output

Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.

Sample Input

6
1 2 5 4 6 2

Sample Output

4

Note

Dãy con dài nhất là dãy \(A_1 = 1 < A_2 = 2 < A_4 = 4 < A_5 = 6\), độ dài dãy này là \(4\).

Download test và solution tại đây.