Вставка ключових значень#5215

Вставка ключових значень

2 секунди

64 мегабайти

Легка

Вас найняла на роботу компанія MacroHard, щоб ви розробили нову структуру даних для збереження цілих ключових значень.

Ця структура виглядає як масив $A$ нескінченної довжини, комірки якого нумеруються з одиниці. Спочатку усі комірки порожні. Єдина операція, яку необхідно підтримувати - це операція $I n ser t (L, K)$ Insert(L, K), де $L$ - положення у масиві, а $K$ - деяке додатне ціле ключове значення.

Операція виконується наступним чином:

Якщо комірка $A_{L}$ A_L порожня, то присвоїти $A_{L} := K$ A_L := K.
Якщо комірка $A_{L}$ A_L не порожня, виконати $I n ser t (L + 1, A_{L})$ Insert(L+1, A_L), а потім присвоїти $A_{L} := K$ A_L := K.

За заданою послідовністю із $N$ цілих чисел $L_{1}, L_{2}, \dots, L_{N}$ L_1, L_2, \ldots, L_N вам необхідно вивести вміст цього масиву після виконання наступної послідовності операцій:

$I n ser t (L_{1}, 1)$ Insert(L_1, 1)

$I n ser t (L_{2}, 2)$ Insert(L_2, 2)

$\dots$

$I n ser t (L_{N}, N)$ Insert(L_N, N)

Вхідні дані

У першому рядку вхідного файла міститься $N$ - кількість операцій $I n ser t$ та $M$ - максимальний номер позиції, яку можна використовувати в операції $I n ser t$ . ( $1 \leq N \leq 131072$ 1 \leq N \leq 131072, $1 \leq M \leq 131072$ 1 \leq M \leq 131072). У наступному рядку задано $N$ цілих чисел $L_{i}$ L_i, які описують операції $I n ser t$ ( $1 \leq L_{i} \leq M$ 1 \leq L_i \leq M).

Вихідні дані

Виведіть вміст масиву після виконання заданої послідовності операцій $I n ser t$ . У першому рядку виведіть $W$ - номер останньої не вільної позиції у масиві. Далі виведіть $W$ цілих чисел - $A_{1}, A_{2}, \dots, A_{W}$ A_1, A_2, \ldots, A_W. Для порожніх комірок виводьте нулі.

Приклади

Приклад 1