Heidi and Library (medium)

小明有一个图书馆。他同时知道，在时间 i ，会有人来借书 a[i]，同时在当天把书还回来。他可以在借书的前一天晚上买书，花费1元。 有的a[i]会是相同的数字，表示有的书会有人在不同的天借阅。 他的图书馆最多只能装k本书，所以当他的存书超过k，他就要把多余的书扔掉。一本书扔掉后，如果有人借，他就需要花费1元重新购买。 给定所有将来的 i 和 a[i]，请问小明最少需要多少钱，才能满足所有人的借书需要？ 感谢@渣儿 提供的翻译

Whereas humans nowadays read fewer and fewer books on paper, book readership among marmots has surged. Heidi has expanded the library and is now serving longer request sequences.

Same as the easy version, but the limits have changed: $ 1<=n,k<=400000 $ .

Same as the easy version.

4 100
1 2 2 1

2

4 1
1 2 2 1

3

4 2
1 2 3 1

3