时间限制：1秒　　内存限制：256M

---

【题目描述】

　　给定长度为\(n\)的序列\(a_1,a_2…,a_n\)。你可以进行如下的操作：
　　　◆设当前序列为 \(b_1,b_2,…,b_m\)；
　　　◆选择 \(1≤i<m\)，将序列变为：\(b_1,b_2,…,b_{i-1},b_i+b_{i+1},b_{i+2},…,b_m\)。
　　目标是让原序列变成不降，即 \(a_i≤a_{i+1}\)。求出这样的序列的最大长度，并构造一个合法序列。

【输入格式】

　　第一行是一个正整数\(n（1≤n≤5000）\)。第二行是\(n\)个正整数 \(a_i（1≤a_i≤10^9）\)。

【输出格式】

　　第一行输出一个正整数\(m\)，表示最终序列的最长长度。
　　第二行输出\(m\)个正整数，表示操作后得到的序列。(没有 Special Judge,不输出这一行)

【输入输出样例1】

　Input

6
3 2 6 3 3 8 

　Output

4
5 6 6 8 //没有 Special Judge,不输出这一行

【样例1说明】

　　[3,2,6,3,3,8] → [5,6,3,3,8] → [5,6,6,8]。

【输入输出样例2】

　Input

7
3 6 4 2 6 2 5

　Output

5
3 6 6 6 7  //没有 Special Judge,不输出这一行

【测试点性质】

　　（10 分）：\(n≤20\)；
　　（15分）：\(n≤100，a_i≤100\)；
　　（20 分）：\(n≤500\)；
　　（25 分）：\(n≤1000\)；
　　（40 分）：无额外限制。

【来源】

　　Mr.he