LIQ - Dãy con tăng dài nhất (bản dễ)

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à một dãy A[i1], A[i2], ..., A[ik] thỏa mãn:

• i1 < i2 < ... < ik
• 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 đã cho có bao nhiêu phần tử.

Input

• Dòng 1 gồm một số nguyên N (1 ≤ N ≤ 1000).
• Dòng 2 ghi N số nguyên A[1], A[2], ..., A[N] (1 ≤ A[i] ≤ 10000).

Output

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

Ví dụ

Input

6
1 2 5 4 6 2

Output

4

Giải thích: Dãy con dài nhất là A[1] = 1 < A[2] = 2 < A[4] = 4 < A[5] = 6, độ dài bằng 4.

Gợi ý

Sử dụng quy hoạch động:

• F[i]: Độ dài dãy con tăng dài nhất mà phần tử cuối cùng là A[i].