← 返回题目列表

Codeforces · 926/E

E. 合并相等元素

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

给定一个正整数序列 a1, a2, ..., an。

如果可能,您可以执行以下操作:查找一对相等的连续元素。如果有多个这样的对,则找到最左边的(具有最小元素索引)。如果两个整数等于 x,则删除这两个整数并在其位置插入一个整数 x + 1。这样,序列中的元素数量在每一步都会减少 1。

当不存在一对相等的连续元素时,停止执行操作。

例如,如果初始序列是 [5, 2, 1, 1, 2, 2],那么在第一个操作之后您将得到 [5, 2, 2, 2, 2],在第二个操作之后 — [5, 3, 2, 2],在第三个操作之后 — [5, 3, 3],最后在第四个操作之后您将得到 [5, 4]。之后,序列中不再有相等的连续元素,因此您停止该过程。

确定停止执行操作后的最终顺序。

输入

第一行包含一个整数 n (2 ≤ n ≤ 2·105) — 序列中元素的数量。

第二行包含整数序列 a1, a2, ..., an (1 ≤ ai ≤ 109)。

输出

在第一行中打印一个整数 k — 停止执行操作后序列中的元素数量。

在第二行中打印 k 个整数 - 停止执行操作后的序列。

示例

输入 #1

6
5 2 1 1 2 2

输出 #1

2
5 4

输入 #2

4
1000000000 1000000000 1000000000 1000000000

输出 #2

1
1000000002

输入 #3

7
4 10 22 11 12 5 6

输出 #3

7
4 10 22 11 12 5 6

注意

第一个示例在语句中进行了描述。

在第二个示例中,初始序列为 [1000000000, 1000000000, 1000000000, 1000000000]。第一次操作后,序列等于 [1000000001, 1000000000, 1000000000]。第二次操作后序列为 [1000000001, 1000000001]。第三次操作后序列为 [1000000002]。

在第三个示例中,最初不存在两个相等的连续元素,因此序列不会改变。