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 < 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ử.

Dữ liệu vào

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

Kết quả

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

6
1 2 5 4 6 2

4

Nguồn: vn.spoj