Đề bài

Cho một dãy số nguyên gồm $N$ phần tử$A_1, A_2, ..., A_N$. Hãy tìm độ dài của dãy con tăng dài nhất (không cần liên tiếp) của dãy số đã cho.

Dãy con tăng là dãy $A_{i_1}, A_{i_2},..., A_{i_k}$ sao cho $i_1 < i_2 < ... < i_k$ và $A_{i_1} < A_{i_2}< ... < A_{i_k}$.

Dữ liệu vào

Dòng 1: Số nguyên dương $N$ ($1 \le N \le 1000$). Dòng 2: Dãy số $A$ gồm $N$ số nguyên ($|A_i| \le 10^9$).

Dữ liệu ra

Một số nguyên duy nhất là độ dài dãy con tăng dài nhất.

Ví dụ