Merge Equal Elements
Contest: VK Cup 2018 - Wild-card Round 1
Difficulty rating: 1900
Tags: constructive algorithms, data structures

You are given a sequence of positive integers a1, a2, ..., an.

While possible, you perform the following operation: find a pair of equal consecutive elements. If there are more than one such pair, find the leftmost (with the smallest indices of elements). If the two integers are equal to x, delete both and insert a single integer x + 1 on their place. This way the number of elements in the sequence is decreased by 1 on each step.

You stop performing the operation when there is no pair of equal consecutive elements.

For example, if the initial sequence is [5, 2, 1, 1, 2, 2], then after the first operation you get [5, 2, 2, 2, 2], after the second — [5, 3, 2, 2], after the third — [5, 3, 3], and finally after the fourth you get [5, 4]. After that there are no equal consecutive elements left in the sequence, so you stop the process.

Determine the final sequence after you stop performing the operation.

Input format:
The first line contains a single integer n (2 ≤ n ≤ 2·105) — the number of elements in the sequence.

The second line contains the sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 109).

Output format:
In the first line print a single integer k — the number of elements in the sequence after you stop performing the operation.

In the second line print k integers — the sequence after you stop performing the operation.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
The first example is described in the statements.

In the second example the initial sequence is [1000000000, 1000000000, 1000000000, 1000000000]. After the first operation the sequence is equal to [1000000001, 1000000000, 1000000000]. After the second operation the sequence is [1000000001, 1000000001]. After the third operation the sequence is [1000000002].

In the third example there are no two equal consecutive elements initially, so the sequence does not change.

Example input:
6
5 2 1 1 2 2

Example output:
2
5 4

Example input:
4
1000000000 1000000000 1000000000 1000000000

Example output:
1
1000000002

Editorial:
Будем складывать все заданные числа в вектор a. Пусть очередное считанное число равно x. Тогда пока x равно последнему числу в векторе, будем удалять последнее число из вектора и увеличивать x на единицу. Когда x стало не равно последнему элементу вектора, добавим его в вектор a и перейдем к следующему числу. После считывания и обрабатывания всех чисел нужно просто вывести элементы вектора a.
Также данная задача имело другое решение. Оно более стандартное, но пишется сложнее, чем предыдущее.
Для решения нам понадобится два массива l и r, а также set eq. В l[i] будет храниться позиция ближайшего неудаленного соседа слева, либо  - 1, если такого нет. В r[i] будет храниться позиция ближайшего неудаленного соседа справа, либо  - 1, если такого нет. В eq будут храниться левые позиции всех соседних пар одинаковых элементов на текущий момент. Также нам понадобиться массив del, где мы будем помечать удаляемые позиции.
Проинициализируем l и r, а также положим в eq все i такие, что a[i] = a[i + 1].
Пока eq не пустой будем выполнять следующее. Достанем из начала eq позицию pos. Это левая позиция самой левой пары одинаковых элементов, а правая позиция этой пары равна r[pos]. Удалим pos из eq. Увеличим a[pos] на единицу, так как мы будем удалять текущую пару чисел, а вместо нее добавлять новое число a[pos] + 1 (фактически, мы удаляем правое число, а левое увеличиваем на единицу). Присвоим del[r[pos]] значению true, так как мы удаляем правое число из текущей пары. Если в eq содержалось значение r[pos], то его нужно удалить, так как теперь этого числа нет.
Теперь нужно пересчитать значения l и r следующим образом: r[pos] = r[r[pos]] и l[r[r[pos]]] = pos.
Теперь у числа в позиции pos новый сосед справа (если он был у r[pos]), а также значение a[pos] могло стать равным значению a[l[pos]]. Поэтому в eq нужно добавить значение l[pos], если a[pos] имеет левого соседа и стало ему равно. Также нужно добавить в eq значение r[pos], если a[pos] теперь имеет нового правого соседа и равно ему.
После того, как eq стал пустым, нужно с помощью массива взять все a[i], которые неудалены. Это можно сделать с помощью массива del — просто взять все такие i, что del[i] имеет значение false, так как это указывает на то, что число в позиции i не было удалено.