CF1234B2.Social Network (hard version)

The only difference between easy and hard versions are constraints on $n$ and $k$.

You are messaging in one of the popular social networks via your smartphone. Your smartphone can show at most $k$ most recent conversations with your friends. Initially, the screen is empty (i.e. the number of displayed conversations equals $0$).

Each conversation is between you and some of your friends. There is at most one conversation with any of your friends. So each conversation is uniquely defined by your friend.

You (suddenly!) have the ability to see the future. You know that during the day you will receive $n$ messages, the $i$-th message will be received from the friend with ID $id_i$ ($1 \le id_i \le 10^9$).

If you receive a message from $id_i$ in the conversation which is currently displayed on the smartphone then nothing happens: the conversations of the screen do not change and do not change their order, you read the message and continue waiting for new messages.

Otherwise (i.e. if there is no conversation with $id_i$ on the screen):

• Firstly, if the number of conversations displayed on the screen is $k$, the last conversation (which has the position $k$) is removed from the screen.
• Now the number of conversations on the screen is guaranteed to be less than $k$ and the conversation with the friend $id_i$ is not displayed on the screen.
• The conversation with the friend $id_i$ appears on the first (the topmost) position on the screen and all the other displayed conversations are shifted one position down.

Your task is to find the list of conversations (in the order they are displayed on the screen) after processing all $n$ messages.

简单版本与困难版本的唯一区别在于 $n$ 和 $k$ 的约束条件。

你正通过智能手机在某个流行的社交网络上与朋友聊天。你的智能手机最多可显示你与朋友之间最近的 $k$ 场对话。初始时，屏幕为空（即显示的对话数量为 $0$）。

每场对话都发生在你与某位朋友之间。你与任意一位朋友之间至多只有一场对话。因此，每场对话可由该朋友的 ID 唯一确定。

你（突然地！）获得了预知未来的能力。你知道当天将收到 $n$ 条消息，其中第 $i$ 条消息来自 ID 为 $id_i$ 的朋友（$1 \le id_i \le 10^9$）。

• 若你从朋友 $id_i$ 处收到一条消息，且该朋友当前正在屏幕上显示其对话，则不发生任何变化：屏幕上的对话列表及其顺序均保持不变，你阅读该消息后继续等待新消息。
• 否则（即屏幕上当前没有与朋友 $id_i$ 的对话）：
  • 首先，若屏幕上已显示 $k$ 场对话，则移除位于屏幕最末（位置为 $k$）的那场对话；
  • 此时，屏幕上对话数量必小于 $k$，且与朋友 $id_i$ 的对话尚未显示；
  • 与朋友 $id_i$ 的对话将出现在屏幕最上方（位置 $1$），其余所有已显示的对话均向下移动一个位置。

你的任务是：在处理完全部 $n$ 条消息后，输出屏幕上显示的对话列表（按其在屏幕上从上到下的顺序）。

The first line of the input contains two integers $n$ and $k$ ($1 \le n, k \le 2 \cdot 10^5)$ — the number of messages and the number of conversations your smartphone can show.

The second line of the input contains $n$ integers $id_1, id_2, \dots, id_n$ ($1 \le id_i \le 10^9$), where $id_i$ is the ID of the friend which sends you the $i$-th message.

输入的第一行包含两个整数 $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$ 表示给你发送第 $i$ 条消息的好友的 ID。

In the first line of the output print one integer $m$ ($1 \le m \le min(n, k)$) — the number of conversations shown after receiving all $n$ messages.

In the second line print $m$ integers $ids_1, ids_2, \dots, ids_m$, where $ids_i$ should be equal to the ID of the friend corresponding to the conversation displayed on the position $i$ after receiving all $n$ messages.

在输出的第一行打印一个整数 $m$（$1 \le m \le \min(n, k)$）—— 表示接收全部 $n$ 条消息后所显示的对话数量。

在第二行打印 $m$ 个整数 $ids_1, ids_2, \dots, ids_m$，其中 $ids_i$ 应等于接收全部 $n$ 条消息后，位于第 $i$ 个位置的对话所对应的联系人的 ID。

In the first example the list of conversations will change in the following way (in order from the first to last message):

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

In the second example the list of conversations will change in the following way:

• $[]$;
• $[2]$;
• $[3, 2]$;
• $[3, 2]$;
• $[1, 3, 2]$;
• and then the list will not change till the end.

在第一个例子中，对话列表将按以下方式变化（按消息从第一到最后一顺序）：

• $[]$；
• $[1]$；
• $[2, 1]$；
• $[3, 2]$；
• $[3, 2]$；
• $[1, 3]$；
• $[1, 3]$；
• $[2, 1]$。

在第二个例子中，对话列表将按以下方式变化：

• $[]$；
• $[2]$；
• $[3, 2]$；
• $[3, 2]$；
• $[1, 3, 2]$；
• 此后列表将一直保持不变直至结束。