Liên minh châu Âu vừa thông qua một đạo luật mới: kể từ ngày ~01/01/2026~, mọi dãy số đều phải tăng không giảm. Cụ thể hơn, một dãy ~a_1, a_2, \ldots, a_n~ bị xem là không hợp lệ nếu tồn tại chỉ số ~i~ sao cho ~1 \le i < n~ và ~a_i > a_{i+1}~. Nếu không tồn tại chỉ số như vậy thì dãy là hợp lệ.

Ivica vừa nhận được một dãy số làm quà và khá lo lắng vì đạo luật mới. May mắn là cậu nhận ra mình có thể lấy hai phần tử kề nhau bất kỳ rồi thay chúng bằng tổng của chúng. Cụ thể, nếu dãy hiện tại là ~a_1, a_2, \ldots, a_m~, Ivica có thể chọn một chỉ số ~k~ với ~1 \le k < m~ rồi biến dãy thành

~a_1, a_2, \ldots, a_{k-1}, (a_k + a_{k+1}), a_{k+2}, \ldots, a_m~.

Ivica có thể thực hiện thao tác này bao nhiêu lần tùy ý. Mục tiêu của cậu là thu được một dãy hợp lệ có độ dài lớn nhất có thể. Hãy tìm độ dài lớn nhất đó, đồng thời in ra một dãy hợp lệ bất kỳ đạt độ dài cực đại.

Input

Dòng đầu tiên chứa một số nguyên dương ~n~, với ~1 \le n \le 5000~.

Dòng thứ hai chứa ~n~ số nguyên dương ~a_i~, với ~1 \le a_i \le 10^9~.

Output

Dòng đầu tiên in ra một số nguyên ~m~: độ dài lớn nhất của một dãy hợp lệ mà Ivica có thể thu được.

Dòng thứ hai in ra ~m~ số nguyên là một dãy hợp lệ có độ dài ~m~ mà Ivica có thể tạo ra. Nếu có nhiều đáp án, in ra đáp án bất kỳ.

Chấm điểm

• Subtask ~1~ (~10~ điểm): ~n \le 20~
• Subtask ~2~ (~15~ điểm): ~n \le 100~, ~a_i \le 100~
• Subtask ~3~ (~20~ điểm): ~n \le 500~
• Subtask ~4~ (~25~ điểm): ~n \le 1000~
• Subtask ~5~ (~40~ điểm): Không có ràng buộc bổ sung.

~60\%~ số điểm của mỗi test được tính nếu dòng ~1~ đúng. ~40\%~ còn lại được tính khi cả dòng ~2~ cũng đúng.

Sample Input ~1~

6
3 2 6 3 3 8

Sample Output ~1~

4
5 6 6 8

Sample Input ~2~

7
3 6 4 2 6 2 5

Sample Output ~2~

5
3 6 6 6 7

Giải thích

• Ví dụ ~1~: Trước tiên, Ivica gộp ~2~ phần tử đầu tiên để thu được dãy ~[5, 6, 3, 3, 8]~, vẫn chưa hợp lệ. Sau đó cậu gộp phần tử thứ ~3~ và thứ ~4~, nhận được dãy ~[5, 6, 6, 8]~. Có thể chứng minh rằng đây là một dãy hợp lệ có độ dài lớn nhất có thể tạo ra từ dãy ban đầu.