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

Difficulty: interview

Starter code:

Solutions:
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() # book_id -> index
next = [n+1] * n # index of next with the same value
inactive_ids = set() # set of inactive object id()s
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):
	# print("book_id=%s, h=%s, inactive=%s" %(book_id, h, inactive_ids))
	if book_id in cache:
		previous_record = book_to_record[book_id]
		inactive_ids.add(id(previous_record))
		serve_book(book_id, i)
		# print('--> Serve book from library ', book_id)
		continue

	if len(cache) < k:
		cost += 1
		serve_book(book_id, i)
		# print('--> Buy book', book_id)
		continue

	while True:
		item = heapq.heappop(h)
		if id(item) in inactive_ids:
			# print("--> Ignore record", item)
			inactive_ids.remove(id(item))
			continue
		cache.remove(item.book_id)
		serve_book(book_id, i)
		cost += 1
		# print('--> Throw away book', item.book_id)
		# print('--> Add book to libary', book_id)
		break
	# print("To evict %s" % to_evict)
	

print(cost)





# 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)