I found an interesting problem on https://codeforces.com/problemset/problem/802/B:
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.


-----Input-----

Same as the easy version, but the limits have changed: 1 ≤ n, k ≤ 400 000.


-----Output-----

Same as the easy version.


-----Examples-----
Input
4 100
1 2 2 1

Output
2

Input
4 1
1 2 2 1

Output
3

Input
4 2
1 2 3 1

Output
3

I tried it in Python, but could not do it. Can you solve it?
# https://codeforces.com/problemset/problem/802/B
import heapq

n, k  = map(int, input().split())
a     = list(map(int, input().split()))
d     = {}
pos   = {}
Q     = []
cnt   = 0

for i, x in enumerate(a):
    if x not in pos:
        pos[x] = []
    pos[x].append(i)
    
for i, x in enumerate(a):
   
    if x not in d:
        cnt += 1
        
        if len(d) == k:
            pos_, x_ = heapq.heappop(Q)
            del d[x_]
        d[x] = 1
        
    pos[x].pop(0)
    
    if len(pos[x]) > 0:
        heapq.heappush(Q, (-pos[x][0], x))
    else:
        heapq.heappush(Q, (-float('inf'), x))   
        
print(cnt)