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[i1],... A[ik] thỏa mãn
i1 < i2 < ... < ik và A[i1] < A[i2] < .. < A[ik].
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 ≤ N ≤ 1000).
- Dòng thứ 2 ghi N số nguyên A[1], A[2], .. A[N] (1 ≤ A[i] ≤ 10000).
Ghi ra độ dài của dãy con tăng đơn điệu dài nhất.
Dãy đã cho trong ví dụ 1 là một dãy giảm nên dãy con tăng chỉ có thể là một dãy có duy nhất 1 phần tử!
Trong ví dụ 2, có nhiều dãy con có độ dài là 3, cụ thể là:(6,8,14) hoặc (2,8,14)