题目背景

本题满分 $110$。

题目描述

给定长度为 $n$ 的序列 $a_1,\ldots,a_n$。

你可以进行如下的操作：

操作

设当前序列为 $[b_1,b_2,\ldots,b_m]$。

选择 $1\le i\lt m$，将序列变为 $[b_1,b_2,\ldots,b_{i-1},b_i+b_{i+1},b_{i+2},\ldots,b_m]$。

目标是让 $a$ 不降，即 $a_{i}\le a_{i+1}$。求出这样的 $a$ 的最大长度，并构造一个合法的 $a$。

本题中你可以获得部分分，详见「计分方式」。

输入格式

第一行，一个正整数 $n$（$1\le n\le 5000$）。

第二行，$n$ 个正整数 $a_i$（$1\le a_i\le 10^9$）。

输出格式

第一行，一个正整数 $m$，表示最终序列的最长长度。

第二行，$m$ 个正整数，表示操作后得到的序列。

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

提示

样例解释

样例一解释：$[\textcolor{red}{3,2},6,3,3,8]\to [5,6,\textcolor{red}{3,3},8]\to [5,6,6,8]$。

子任务

• $\text{Subtask 1 (10 pts)}$：$n\le 20$。
• $\text{Subtask 2 (15 pts)}$：$n\le 100,a_i\le 100$。
• $\text{Subtask 3 (20 pts)}$：$n\le 500$。
• $\text{Subtask 4 (25 pts)}$：$n\le 1000$。
• $\text{Subtask 5 (40 pts)}$：无额外限制。

计分方式

正确回答第一行可以获得 $60\%$ 的分数。

在正确回答第一行的基础上正确回答第二行可以获得剩下 $40\%$ 的分数。

如果只想要获得 $60\%$ 的分数，也要在第二行输出 $m$ 个正整数，否则可能使得分出现偏差。