Cho một 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 mãn \(i_1 \lt i_2 \lt ... \lt i_k\) và \(A_{i_1} \lt A_{i_2} ... \lt 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ử.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương \(N (1 \le N \le 30000)\)
• Dòng thứ \(2\) ghi \(N\) số nguyên \(A_1,A_2...A_N\)

Dữ liệu ra

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

Input 1

6
1 2 5 4 6 2

Output 1

4