Dãy con tăng dài nhất (LIS)

Cho mảng số nguyên A[] gồm N phần tử, hãy tìm dãy con (không nhất thiết các phần tử phải liên tiếp) tăng chặt dài nhất của mảng A.

Input Format

Dòng đầu tiên là N; Dòng thứ 2 gồm N phần tử của mảng A(1<=N<=1000; 1<=A[i]<=1000)

Constraints

.

Output Format

In ra độ dài của dãy con tăng dài nhất.

Ví dụ:

Dữ liệu vào

7
1 2 7 4 5 6 3

Dữ liệu ra

5