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

Cho một dãy số nguyên gồm \(n\) phần tử \(a_1, a_2, \ldots, a_n\).
Hãy tìm độ dài của dãy con tăng dài nhất.

Một dãy con là dãy thu được bằng cách xoá đi một số phần tử (có thể là không phần tử nào),
mà không thay đổi thứ tự các phần tử còn lại.
Dãy con được gọi là tăng nếu mọi phần tử đứng sau lớn hơn (hẳn) phần tử đứng trước.

Input

• Dòng đầu tiên chứa một số nguyên \(n\) (\(1 \le n \le 10^3\)).

• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \ldots, a_n\) (\(1 \le a_i \le 10^9\)).

Output

In ra một số nguyên duy nhất --- độ dài của dãy con tăng dài nhất.

Scoring

• Có \(50\%\) số điểm ứng với \(n \le 20\).