Gửi bài giải
Điểm:
10,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Cho dãy số nguyên ~A = {a_1, a_2, ..., a_n}~. Một dãy con của dãy A là một cách chọn ra trong A một số phần tử giữ nguyên thứ tự. Như vậy A có ~2^n~ dãy con.
Yêu cầu:
Tìm dãy con đơn điệu tăng của A có độ dài lớn nhất. Tức là tìm một số K lớn nhất sao cho tồn tại một dãy chỉ số ~i_1 < i_2 < ... < i_k ~ sao cho ~a_{i_1} < a_{i_2} < ... < a_{i_k}~
Dữ liệu:
Dòng đầu chứa số nguyên n ~(n \le 10^5)~
Dòng tiếp theo chứa n số nguyên ~a_i~ ~(\forall i, |a_i| \le 10^9)~
Kết quả:
Dòng đầu ghi giá trị của K.
Dòng tiếp theo ghi K giá trị ~i_1 < i_2 < ... < i_k ~, các số cách nhau một dấu khoảng trắng.
Trong trường hợp có nhiều dãy con tăng có cùng độ dài thì xuất dãy con hợp lệ tùy ý.
Input:
12
1 2 3 8 9 4 5 6 2 3 9 10
Output:
8
1 2 3 6 7 8 11 12
Bình luận