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

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Data structures

Greedy algorithms


Solutions:
import sys
input = sys.stdin.readline
from collections import deque, defaultdict
from heapq import heappush, heappop
(n, k) = map(int, input().split())
A = list(map(int, input().split()))
dic = defaultdict(deque)
for (i, a) in enumerate(A):
	dic[a].append(i)
hp = []
S = set()
ans = 0
for (i, a) in enumerate(A):
	dic[a].popleft()
	if a not in S:
		if len(S) < k:
			S.add(a)
			ans += 1
		else:
			idx = heappop(hp)[1]
			S.discard(idx)
			S.add(a)
			ans += 1
	if dic[a]:
		heappush(hp, (-dic[a][0], a))
	else:
		heappush(hp, (float('-inf'), a))
print(ans)


import sys
import heapq
from collections import namedtuple
Record = namedtuple('Record', ['index', 'book_id'])
l1 = sys.stdin.readline()
l2 = sys.stdin.readline()
(n, k) = list(map(int, l1.split(' ')))
books = list(map(int, l2.split(' ')))
cost = 0
cache = set()
prev = dict()
next = [n + 1] * n
inactive_ids = set()
book_to_record = dict()

def serve_book(book_id, i):
	cache.add(book_id)
	record = Record(-next[i], book_id)
	heapq.heappush(h, record)
	book_to_record[book_id] = record
h = []
for (i, book_id) in enumerate(books):
	if book_id in prev:
		next[prev[book_id]] = i
	prev[book_id] = i
for (i, book_id) in enumerate(books):
	if book_id in cache:
		previous_record = book_to_record[book_id]
		inactive_ids.add(id(previous_record))
		serve_book(book_id, i)
		continue
	if len(cache) < k:
		cost += 1
		serve_book(book_id, i)
		continue
	while True:
		item = heapq.heappop(h)
		if id(item) in inactive_ids:
			inactive_ids.remove(id(item))
			continue
		cache.remove(item.book_id)
		serve_book(book_id, i)
		cost += 1
		break
print(cost)


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)