B2. Социальная сеть (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между простой и сложной версиями — ограничения на $$$n$$$ и $$$k$$$.

Вы общаетесь в одной из популярных социальных сетей, используя свой смартфон. Ваш смартфон может показывать не более $$$k$$$ самых недавних бесед с вашими друзьями. Изначально экран смартфона пуст (то есть количество показанных бесед равно $$$0$$$).

Каждая беседа — это ваш диалог с каким-то из ваших друзей. Всего существует не более одной беседы с каждым из ваших друзей. Таким образом, каждая беседа однозначно определяется вашим другом.

Вы (внезапно!) обладаете возможностью видеть будущее. Вы знаете, что в течение дня вы получите $$$n$$$ сообщений, $$$i$$$-е сообщение будет получено от друга с ID $$$id_i$$$ ($$$1 \le id_i \le 10^9$$$).

Если вы получаете сообщение от друга $$$id_i$$$ тогда, когда беседа с ним сейчас показана на экране смартфона, то ничего не происходит: беседы на экране не меняются и не меняют свой относительный порядок, вы просто читаете сообщение и продолжаете ждать новых сообщений.

Иначе (то есть тогда, когда на экране нет беседы с другом $$$id_i$$$):

  • Сначала, если количество бесед, отображенных на экране, равно $$$k$$$, последняя беседа (которая имеет позицию $$$k$$$) удаляется с экрана.
  • Теперь количество бесед на экране гарантированно меньше $$$k$$$ и беседа с другом $$$id_i$$$ не отображена на экране.
  • Беседа с другом $$$id_i$$$ появляется на первой (верхней) позиции на экране и все другие отображенные беседы сдвигаются на одну позицию вниз.

Ваша задача — найти список бесед (в порядке, в котором они будут отображены на экране) после обработки всех $$$n$$$ сообщений.

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n, k \le 2 \cdot 10^5)$$$ — количество сообщений и количество бесед, которые может показывать ваш смартфон.

Вторая строка входных данных содержит $$$n$$$ целых чисел $$$id_1, id_2, \dots, id_n$$$ ($$$1 \le id_i \le 10^9$$$), где $$$id_i$$$ равно ID друга, который отправит вам $$$i$$$-е сообщение.

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

В первой строке выходных данных выведите одно целое число $$$m$$$ ($$$1 \le m \le min(n, k)$$$) — количество бесед, показанных на экране после получения всех $$$n$$$ сообщений.

Во второй строке выходных данных выведите $$$m$$$ целых чисел $$$ids_1, ids_2, \dots, ids_m$$$, где $$$ids_i$$$ должно быть равно ID друга, соответствующего беседе, отображенной на позиции $$$i$$$ после получения всех $$$n$$$ сообщений.

Примеры
Входные данные
7 2
1 2 3 2 1 3 2
Выходные данные
2
2 1
Входные данные
10 4
2 3 3 1 1 2 1 2 3 3
Выходные данные
3
1 3 2
Примечание

В первом тестовом примере список бесед будет изменяться следующим образом (в порядке от первого к последнему сообщению):

  • $$$[]$$$;
  • $$$[1]$$$;
  • $$$[2, 1]$$$;
  • $$$[3, 2]$$$;
  • $$$[3, 2]$$$;
  • $$$[1, 3]$$$;
  • $$$[1, 3]$$$;
  • $$$[2, 1]$$$.

Во втором тестовом примере список бесед будет изменяться следующим образом:

  • $$$[]$$$;
  • $$$[2]$$$;
  • $$$[3, 2]$$$;
  • $$$[3, 2]$$$;
  • $$$[1, 3, 2]$$$;
  • и затем список не изменится до самого конца.