Social Network (hard version)

注：*简单版*与*困难版*的区别只是$n$和$k$的数据约束不同。 你正在通过你的手机在一个流行社交网络（朋友圈）之中发信息。你的手机可以同时展示至多$k$个你与你的朋友的最近通话记录。起初，手机的屏幕上是空的（即显示的通话记录数量为$0$）。 每次通话都是你与你的朋友进行的。而且你与你的任何一个朋友至多只会通话一次，所以每次通话都是和你的朋友一一对应、唯一定义的。 你（突然之间！！！）得到了预知未来的能力。你知道在一天当中你将会收到$n$条信息，第$i$条信息将会是来自编号为$id_i$的朋友的（$1 \le id_i \le 10^9$）。 如果你收到的一条来自$id_i$的朋友的信息并且这个朋友已经在你手机屏幕所显示的通话记录中存在了，那么什么都不会发生：屏幕上的记录不会改变，顺序也不会被改变，你只是读了这个信息之后等待一条新的信息。 然而（在屏幕上没有显示与发来信息的朋友$id_i$的通话记录）： - 首先，如果屏幕上显示的通话记录的数目为$k$，那么将在屏幕中清除最后一个通话记录（位置为$k$）。 - 现在屏幕上的记录数目一定小于$k$并且编号为$id_i$的朋友也没有出现在你手机屏幕上的通话记录当中。 - 你与编号为$id_i$的朋友的通话记录将出现在屏幕上列表的第一个（最上边）的位置，其他的通话记录都将向后移动一个位置。 你的任务就是在处理完这所有的$n$条信息之后找到这时通话记录的列表（按照他们在屏幕上显示的顺序）。

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.

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.

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.

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 

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.