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 tìm một dãy con tăng của dãy a₁, a₂, …, a_N có nhiều phần tử nhất (dài nhât)?

Dữ liệu vào:

• Dòng đầu chứa số nguyên N.
• Dòng thứ 2 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:

• Dòng đầu ghi ra số phần tử của dãy con tăng dài nhất của dãy a₁, a₂, …, a_N
• Dòng thứ 2 ghi ra một dãy con tăng dài nhất của dãy a₁, a₂, …, a_N. Nếu có nhiều dãy con tăng có cùng số phần tử (nhiều nhất) thì ghi ra một dãy bất kỳ.

Ví dụ:

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

Dữ liệu ra:
4
1 2 4 6

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⁹