THỰC HÀNH

Cho một dãy số nguyên gồm N phần tử a₁, a₂, …, a_N. Một dãy con đơn điệu tăng của dãy trên là dãy a_i1, a_i2, …, a_ik sao cho: i₁ < i₂ < … < i_k và a_i1 < a_i2 < … < a_ik. Hãy cho biết dãy con đơn điệu tăng của dãy đã cho có nhiều nhất bao nhiêu số hạng?

Dữ liệu vào:

• Dòng đầu chứa số nguyên N.
• Dòng thứ hai chứa N số nguyên dương a₁, a₂, …, a_N, mỗi số cách nhau bởi một dấu cách.

Dữ liệu ra:

Ghi ra độ dài của dãy con đơn điệu tăng dài nhất.

Ví dụ:

Dữ liệu vào:
6
1 2 5 4 6 2

Dữ liệu ra:
4

Giải thích test ví dụ: Dãy con tăng dài nhất là dãy 1, 2, 4, 6 độ dài dãy này là 4.

Giới hạn: 1 ≤ n ≤ 1000, -10⁹ ≤ a_i ≤ 10⁹