Задача №114650. Игра с массивом
Родители Пети никогда не отличались оригинальностью, поэтому на Новый год Петя в очередной раз получил в подарок массив из n целых чисел. К счастью, Петя вырос гораздо более изобретательным человеком, чем его родители, поэтому снова смог придумать игру с массивом, которая поможет ему скоротать долгие зимние вечера.
Во время игры Петя может выполнить несколько (возможно ноль) операций следующего вида: выбрать в массиве два соседних числа, отличающихся на 1 , и заменить их на одно новое число, равное максимальному из этих чисел плюс один. Например, если у Пети есть массив [1, 4, 3, 7] , то он может выбрать числа 3 и 4 и заменить их на число 5 , получив массив [1, 5, 7] , аналогично, если у Пети есть массив [2, 3] , он может получить из него массив [4] за одну операцию. Однако, если у Пети есть массив [1, 3, 5, 2] , то он не может выполнить с ним ни одной операции, в частности не может выбрать пару чисел 1 и 2 , так как они не находятся в массиве рядом.
Петя не любит длинные массивы, поэтому ему стало интересно, какой минимальной длины массива он может достичь, выполнив с ним некоторое количество операций, описанных выше.
В первой строке находится одно целое число n ( 1 ≤ n ≤ 10 6 ) — длина массива.
Во второй строке находятся n целых чисел a i ( 1 ≤ a i ≤ 40 ) — элементы массива, который подарили Пете.
В первой строке выведите одно число k — минимальную длину массива, которую Петя может получить в результате применения операций, описанных выше.
Во второй строке выведите k чисел — элементы массива, который Петя может получить. Если массивов минимальной длины, которые Петя может получить, несколько, выведите любой.
В первом примере Петя может выбрать числа 2 и 3 и заменить их на число 4 , получив тем самым массив [1, 4] . Также Петя может выбрать числа 1 и 2 , получив тем самым массив [3, 3] . Оба способа позволяют Пете получить массив длины 2 , массив длины 1 Петя получить не может.
Во втором примере Петя может действовать так:
.
Тесты к этой задаче состоят из трёх групп. Баллы за каждую группу ставятся только при прохождении всех тестов группы и всех тестов предыдущих групп.
| Дополнительные ограничения | |||
| Группа | Баллы | n | Комментарий |
| 0 | 0 | – | Тесты из условия. |
| 1 | 37 | n ≤ 500 | |
| 2 | 23 | n ≤ 5000 | |
| 3 | 40 | – |
3 1 2 3
2 1 4
5 2 1 2 3 1
2 5 1