← 返回题目列表

Codeforces · 962/D

D. 合并等于

中文机器翻译题面 查看原题

给你一个正整数数组。当至少有两个相等的元素时,我们将执行以下操作。我们选择数组 $$$2$$$ 或多次出现的最小值 $$$x$$$。取此数组中 $$$x$$$ 的前两次出现(最左边的两次出现)。删除左侧的这两个值,右侧的值替换为这两个值的总和(即 $$$2 \cdot x$$$)。

确定执行所描述的操作后数组的外观。

例如,假设给定的数组看起来像 $$$[3, 4, 1, 2, 2, 1, 1]$$$。它将按以下方式更改:$$$[3, 4, 1, 2, 2, 1, 1]~\rightarrow~[3, 4, 2, 2, 2, 1]~\rightarrow~[3, 4, 4, 2, 1]~\rightarrow~[3, 8, 2, 1]$$$。

如果给定的数组看起来像 $$$[1, 1, 3, 1, 1]$$$,它将按以下方式更改:$$$[1, 1, 3, 1, 1]~\rightarrow~[2, 3, 1, 1]~\rightarrow~[2, 3, 2]~\rightarrow~[3, 4]$$$。

输入

第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 150\,000$$$) — 数组中的元素数量。

第二行包含 $$$n$$$ 元素的序列 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$) — 数组的元素。

输出

在第一行打印一个整数 $$$k$$$ — 所有执行操作后数组中的元素数量。在第二行中打印 $$$k$$$ 整数 - 所有执行操作后的数组元素。

示例

输入 #1

7
3 4 1 2 2 1 1

输出 #1

4
3 8 2 1

输入 #2

5
1 1 3 1 1

输出 #2

2
3 4

输入 #3

5
10 40 20 50 30

输出 #3

5
10 40 20 50 30

注意

声明中考虑了前两个示例。

在第三个示例中,给定数组中的所有整数都是不同的,因此它不会改变。