406348: GYM102386 E Отложенные операции

E. Отложенные операцииограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Дима выучил ленивое дерево отрезков, он был восхищен идеей отложенных операций, которая там используется. Он решил использовать эту тактику для решения домашних работ в течение $$$n$$$ дней. У Димы в вузе есть $$$k$$$ разных предметов, пронумерованных от 1 до $$$k$$$. В каждый из $$$n$$$ дней ему приходит задание по одному из этих предметов. То есть в $$$i$$$-ый день он получает задание $$$a_i$$$, где $$$a_i$$$ - номер предмета по которому пришло задание в $$$i$$$-ый день

Дима может провести свой день двумя способами. Он может сделать все накопившиеся домашние работы по одному из $$$k$$$ предметов или не делать ничего.

Помогите Диме составить план выполнения домашних заданий таким образом, чтобы он был занят домашней работой минимально возможное число дней, и при этом к концу $$$n$$$ дней все выданные домашние задания были выполнены.

Входные данные

В первой строке через пробел вводятся целые числа $$$n$$$ и $$$k$$$ — количество дней и количество различных предметов $$$(1\leq n, k\leq 10^5)$$$.

Во второй строке дано $$$n$$$ чисел, разделённых пробелами, где $$$i$$$-е число равно $$$a_i$$$ — номеру предмета, по которому дано задание в $$$i$$$-ый день $$$(1\leq a_i\leq k)$$$. Возможна ситуация, когда задания по некоторым предметам не выдаются Диме ни разу.

Выходные данные

В единственной строке выведите $$$n$$$ чисел, разделённых пробелами, где $$$i$$$-е число должно быть равно 0, если Дима должен бездельничать в $$$i$$$-й день, либо номеру предмета, если Диме стоит выполнить все домашние задания по данному предмету в этот день. Если существует несколько возможных вариантов ответа, выведите любой.

ПримерыВходные данные

3 3
1 2 3

Выходные данные

1 2 3

Входные данные

4 2
1 1 1 1

Выходные данные

0 0 0 1

Примечание

В первом примере Диме каждый день дают задание по новому предмету, поэтому он вынужден каждый день выполнять новое домашнее задание.

Во втором примере Диме четыре дня подряд дают задание типа по предмету номер $$$1$$$, поэтому он может выполнить их все в последний день. В таком случае он сможет бездельничать целых три дня.