欧洲联盟最近通过了一项新法律，规定所有序列都必须是单调不降的。从 2026 年 1 月 1 日开始，任何拥有非单调不降序列的人都将受到严厉处罚。更具体地说，对于一个序列 $a_1, a_2, \dots, a_n$，如果存在某个 $i$ ($1 \le i < n$) 满足 $a_i > a_{i+1}$，则该序列是非法的；否则，该序列是合法的。

Ivica 最近收到了一个序列作为礼物，他担心自己会因为这项新法律而陷入麻烦。幸运的是，Ivica 意识到他可以任选序列中相邻的两个元素，并将它们替换为它们的和。更具体地说，如果 Ivica 当前的序列为 $a_1, a_2, \dots, a_m$，他可以选择某个满足 $1 \le k < m$ 的 $k$，并将序列替换为 $a_1, a_2, \dots, a_{k-1}, (a_k + a_{k+1}), a_{k+2}, \dots, a_m$。Ivica 可以进行任意多次这样的操作，他的目标是通过这些操作获得一个合法的序列。

当然，Ivica 不想完全毁掉他的序列，因此他希望从初始序列中获得一个尽可能长的合法序列。请帮助 Ivica 确定他能从初始序列中获得的最长合法序列的长度，并输出任意一个具有该最大长度的合法序列。

输入格式

第一行包含一个自然数 $n$ ($1 \le n \le 5000$)，表示 Ivica 序列的长度。

第二行包含 $n$ 个自然数 $a_i$ ($1 \le a_i \le 10^9$)，表示 Ivica 收到的礼物序列。

输出格式

第一行输出一个整数 $m$，表示 Ivica 从初始序列中可以获得的最长合法序列的长度。

第二行输出 $m$ 个整数，表示 Ivica 从初始序列中可以获得的一个长度为 $m$ 的合法序列。如果存在多个这样的序列，输出其中任意一个即可。

子任务

对于每个测试用例，如果第一行输出正确，将获得该测试用例 60% 的分数。

如果第二行输出也正确，将获得该测试用例剩余 40% 的分数。

样例

输入 1

6
3 2 6 3 3 8

输出 1

4
5 6 6 8

输入 2

7
3 6 4 2 6 2 5

输出 2

5
3 6 6 6 7

说明

样例 1 解释

在第一次操作中，Ivica 将前两个元素替换为它们的和，得到非法数组 $[5, 6, 3, 3, 8]$。然后，他将第三个和第四个元素替换为它们的和，得到合法数组 $[5, 6, 6, 8]$。可以证明，这是能从初始数组中获得的最长合法数组。