Một dãy là hợp lệ nếu không giảm. Ivica được phép lặp lại thao tác thay hai phần tử kề nhau bằng tổng của chúng. Hãy tạo một dãy hợp lệ có độ dài lớn nhất có thể từ dãy ban đầu và in một dãy đạt độ dài đó.

Dữ liệu vào

Dòng đầu chứa \(n\) (\(1\le n\le5000\)). Dòng hai chứa \(n\) số \(a_i\) (\(1\le a_i\le10^9\)).

Dữ liệu ra

Dòng đầu in độ dài lớn nhất \(m\). Dòng hai in \(m\) phần tử của một dãy hợp lệ có độ dài \(m\) có thể nhận được. Nếu có nhiều đáp án, in một đáp án bất kỳ.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(10\) điểm: \(n\le20\).
2. \(15\) điểm: \(n\le100\), \(a_i\le100\).
3. \(20\) điểm: \(n\le500\).
4. \(25\) điểm: \(n\le1000\).
5. \(40\) điểm: không có ràng buộc thêm.

Với mỗi testcase, dòng đầu đúng nhận 60% số điểm; 40% còn lại chỉ nhận khi dòng hai là một phép gộp hợp lệ tạo dãy không giảm.

Ví dụ

6
3 2 6 3 3 8

4
5 6 6 8

7
3 6 4 2 6 2 5

5
3 6 6 6 7

Nguồn

COCI 2025/2026 - Vòng 2, bài Rastući.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.