Your search for Heidi is over – you finally found her at a library, dressed up as a human. In fact, she has spent so much time there that she now runs the place! Her job is to buy books and keep them at the library so that people can borrow and read them. There are n different books, numbered 1 through n.

We will look at the library's operation during n consecutive days. Heidi knows in advance that on the i-th day (1 ≤ i ≤ n) precisely one person will come to the library, request to borrow the book a_{i}, read it in a few hours, and return the book later on the same day.

Heidi desperately wants to please all her guests, so she will make sure to always have the book a_{i} available in the library on the i-th day. During the night before the i-th day, she has the option of going to the bookstore (which operates at nights to avoid competition with the library) and buying any book for the price of 1 CHF. Of course, if she already has a book at the library, she does not need to buy it again. Initially, the library contains no books.

There is a problem, though. The capacity of the library is k – this means that at any time, there can be at most k books at the library. If buying a new book would cause Heidi to have more than k books, she must first get rid of some book that she already has, in order to make room for the new book. If she later needs a book that she got rid of, she will need to buy that book again.

You are given k and the sequence of requests for books a_1, a_2, ..., a_{n}. What is the minimum cost (in CHF) of buying new books to satisfy all the requests?


-----Input-----

The first line of input will contain two integers n and k (1 ≤ n, k ≤ 80). The second line will contain n integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ n) – the sequence of book requests.


-----Output-----

On a single line print the minimum cost of buying books at the store so as to satisfy all requests.


-----Examples-----
Input
4 80
1 2 2 1

Output
2

Input
4 1
1 2 2 1

Output
3

Input
4 2
1 2 3 1

Output
3



-----Note-----

In the first test case, Heidi is able to keep all books forever. Therefore, she only needs to buy the book 1 before the first day and the book 2 before the second day.

In the second test case, she can only keep one book at a time. Therefore she will need to buy new books on the first, second and fourth day.

In the third test case, before buying book 3 on the third day, she must decide which of the books 1 and 2 she should get rid of. Of course, she should keep the book 1, which will be requested on the fourth day.

Difficulty: MEDIUM_HARD
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
z = [0] * 81
(kz, ans) = (0, 0)
for i in range(n):
	if z[a[i]]:
		continue
	ans += 1
	if k > kz:
		z[a[i]] = 1
		kz += 1
	else:
		h = -1
		for j in range(1, n + 1):
			if z[j]:
				m = n + 1
				for p in range(i, n):
					if j == a[p]:
						m = p
						break
				if m > h:
					h = m
					t = j
		z[t] = 0
		z[a[i]] = 1
print(ans)


import sys

def solve():
	(n, k) = map(int, input().split())
	a = [int(i) - 1 for i in input().split()]
	kinds = len(set(a))
	if kinds <= k:
		print(kinds)
		return
	books = [False] * n
	have = 0
	cost = 0
	for (i, ai) in enumerate(a):
		if books[ai]:
			continue
		elif have < k:
			books[ai] = True
			cost += 1
			have += 1
		else:
			trash = -1
			longest = -1
			for j in range(n):
				if books[j]:
					if j not in a[i + 1:]:
						trash = j
						break
					m = a[i + 1:].index(j)
					if longest < m:
						longest = m
						trash = j
			assert trash != -1
			books[trash] = False
			books[ai] = True
			cost += 1
	print(cost)

def __starting_point():
	solve()
__starting_point()


import sys
input = sys.stdin.readline
from collections import deque, defaultdict
(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)
S = set()
ans = 0
for (i, a) in enumerate(A):
	for d in dic:
		while dic[d] and dic[d][0] <= i:
			dic[d].popleft()
	if a not in S:
		if len(S) < k:
			S.add(a)
			ans += 1
		else:
			day = i
			for s in S:
				if s not in dic or not dic[s]:
					idx = s
					break
				elif dic[s][0] > day:
					day = dic[s][0]
					idx = s
			S.remove(idx)
			S.add(a)
			ans += 1
print(ans)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split())) + [-1]
cost = 0
lib = []
for i in range(n):
	if a[i] in lib:
		continue
	if len(lib) < k:
		lib.append(a[i])
		cost += 1
	else:
		far = 0
		for (ind, j) in enumerate(lib):
			o = i + 1
			while o < n + 1 and a[o] != j:
				o += 1
			if o > far:
				far = min(o, n - 1)
				maxindex = ind
				maxele = j
				if o == n:
					break
		lib[maxindex] = a[i]
		cost += 1
print(cost)


R = lambda : map(int, input().split())
(n, k) = R()
a = list(R())
l = []
m = 0
for i in range(n):
	if a[i] not in l:
		m += 1
		if len(l) < k:
			l.append(a[i])
		else:
			curmin = n
			curindex = 0
			found = [n] * len(l)
			for j in range(len(a[i + 1:])):
				if a[i + j + 1] in l and found[l.index(a[i + j + 1])] == n:
					found[l.index(a[i + j + 1])] = j
			l[found.index(max(found))] = a[i]
print(m)


(n, k) = map(int, input().split())
arr = [int(z) for z in input().split()]
books = set()

def latest(n, arr, i, books):
	w = {}
	for pos in range(i + 1, n):
		if w.get(arr[pos]):
			continue
		else:
			w[arr[pos]] = pos
	for j in books:
		if not w.get(j):
			w[j] = 10 ** 18
	mn = 0
	ltr = 0
	for j in books:
		if w[j] > mn:
			mn = w[j]
			ltr = j
	return ltr
cnt = 0
for i in range(n - 1):
	if arr[i] not in books:
		cnt += 1
		if len(books) + 1 > k:
			l = latest(n, arr, i, books)
			books.remove(l)
		books.add(arr[i])
if arr[-1] not in books:
	cnt += 1
print(cnt)


(n, k) = [int(x) for x in input().split()]
requests = [int(x) for x in input().split()]
req_list = {}

def find_last(bucket):
	last_book = None
	last_date = None
	nonlocal req_list
	i = 0
	for item in bucket:
		if last_book is None:
			last_book = item
			if len(req_list[item]) < 1:
				last_date = float('inf')
				return (item, i)
			else:
				last_date = req_list[item][0]
			index = i
		elif len(req_list[item]) >= 1 and req_list[item][0] > last_date:
			last_book = item
			last_date = req_list[item][0]
			index = i
		elif len(req_list[item]) < 1 and last_date < float('inf'):
			return (item, i)
		i += 1
	return (last_book, index)

def update_reqlist(book):
	nonlocal req_list
	req_list[book] = req_list[book][1:]
for i in range(n):
	if requests[i] in req_list:
		req_list[requests[i]].append(i)
	else:
		req_list[requests[i]] = [i]
bucket = []
bucket_size = 0
cost = 0
for book in requests:
	if book in bucket:
		update_reqlist(book)
		continue
	if bucket_size < k:
		bucket.append(book)
		bucket_size += 1
		cost += 1
		update_reqlist(book)
	else:
		(last_book, index) = find_last(bucket)
		if len(bucket) > 1:
			bucket.pop(index)
		else:
			bucket = []
		bucket.append(book)
		update_reqlist(book)
		cost += 1
print(cost)


(n, k) = map(int, input().split())
a = list(map(int, input().split()))
inventory = set()
bought = 0
for i in range(n):
	if a[i] not in inventory:
		if len(inventory) == k:
			farthest_time = 0
			farthest = 0
			for v in inventory:
				try:
					far = a.index(v, i + 1)
					if far > farthest_time:
						farthest_time = far
						farthest = v
				except ValueError:
					farthest_time = 10000
					farthest = v
			inventory.remove(farthest)
		inventory.add(a[i])
		bought += 1
print(bought)


(n, k) = list(map(int, input().split()))
a = list(map(int, input().split()))
library = []
money = 0
for i in range(len(a)):
	if a[i] not in library:
		money += 1
		if len(library) < k:
			library.append(a[i])
		else:
			curmin = n
			curindex = 0
			found = [n] * len(library)
			for j in range(len(a[i + 1:])):
				if a[i + j + 1] in library and found[library.index(a[i + j + 1])] == n:
					found[library.index(a[i + j + 1])] = j
			library[found.index(max(found))] = a[i]
print(money)


(n, k) = (int(i) for i in input().split())
order = [int(i) for i in input().split()]

def calculateMinCost(n, k, order):
	cost = 0
	books = set()
	for i in range(n):
		if order[i] in books:
			continue
		if len(books) != k:
			cost += 1
			books.add(order[i])
		else:
			lpos = -1
			cc = -1
			for j in books:
				try:
					pos = order[i + 1:].index(j)
				except ValueError:
					cc = j
					break
				if pos > lpos:
					lpos = pos
					cc = j
			books.remove(cc)
			books.add(order[i])
			cost += 1
	print(cost)
calculateMinCost(n, k, order)


(n, k) = (int(i) for i in input().split())
zapross = [int(i) for i in input().split()]
lave = 0
curh = set()
for i in range(n):
	if zapross[i] in curh:
		continue
	if len(curh) != k:
		lave += 1
		curh.add(zapross[i])
	else:
		lpos = -1
		cc = -1
		for j in curh:
			try:
				pos = zapross[i + 1:].index(j)
			except ValueError:
				cc = j
				break
			if pos > lpos:
				lpos = pos
				cc = j
		curh.remove(cc)
		curh.add(zapross[i])
		lave += 1
print(lave)


def dist(a, f, i):
	for j in range(i + 1, len(a)):
		if f == a[j]:
			return j
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
books = set()
l = 0
pref = [0 for i in range(n)]
for i in range(n - 1, -1, -1):
	pref[a[i] - 1] = max(pref[a[i] - 1], i)
res = 0
for i in range(n):
	if a[i] not in books:
		if l == k:
			for j in books:
				if pref[j - 1] < i:
					l -= 1
					books.discard(j)
					break
			if l == k:
				m = -1
				for j in books:
					if dist(a, j, i) > m:
						m = dist(a, j, i)
						ind = j
				books.discard(ind)
				l -= 1
		res += 1
		books.add(a[i])
		l += 1
print(res)


def index(e, l, s):
	res = []
	off = s
	while True:
		try:
			off = l.index(e, off + 1)
		except ValueError:
			break
		else:
			res.append(off)
	if len(res) != 0:
		return res[0]
	else:
		return 10 ** 9
ni = list(map(int, input().strip().split(' ')))
n = ni[0]
k = ni[1]
arr = list(map(int, input().strip().split(' ')))
li = []
cost = 0
if k >= len(set(arr)):
	s = set(arr)
	print(len(s))
else:
	v = 1
	i = 1
	li.append(arr[0])
	while v < k and i < n:
		if arr[i] not in li:
			li.append(arr[i])
			v += 1
		i += 1
	cost = k
	for j in range(i, n):
		if arr[j] not in li:
			mi = 0
			for h in li:
				ind = index(h, arr, j)
				if ind > mi:
					mi = ind
					val = h
			li.remove(val)
			li.append(arr[j])
			cost += 1
	print(cost)


from collections import deque

class Treap:

	def __init__(self, key, priority, prrty_cmprtr):
		self.key = key
		self.priority = priority
		self.priority_comparator = prrty_cmprtr
		self.left = None
		self.right = None

	def merge(self, right):
		if right is None:
			return self
		if self.priority_comparator(self.priority, right.priority):
			root = self
			if root.right is not None:
				root.right = root.right.merge(right)
			else:
				root.right = right
		else:
			root = right
			root.left = self.merge(right.left)
		return root

	def split(self, key):
		if self.key <= key:
			left = self
			if left.right is not None:
				(left.right, right) = left.right.split(key)
			else:
				(left.right, right) = (None, None)
		else:
			right = self
			if right.left is not None:
				(left, right.left) = right.left.split(key)
			else:
				(left, right.left) = (None, None)
		return (left, right)

	def insert(self, element):
		(left, right) = self.split(element.key)
		if left is not None:
			t = left.merge(element)
		else:
			t = element
		if right is not None:
			return t.merge(right)
		return t

	def delete(self, key):
		(left, right) = self.split(key)
		(left, middle) = left.split(key - 1)
		if left is not None:
			return left.merge(right)
		return right

	def find(self, key):
		pos = self
		while True:
			if key == pos.key:
				return True
			elif key < pos.key:
				if pos.left is None:
					return False
				pos = pos.left
			else:
				if pos.right is None:
					return False
				pos = pos.right
(n, k) = map(int, input().split())
a = list(map(int, input().split()))
first = [deque() for i in range(n)]
for i in range(n):
	first[a[i] - 1].append(i)
first[a[0] - 1].popleft()
if not first[a[0] - 1]:
	priority = float('inf')
else:
	priority = first[a[0] - 1][0]
treap = Treap(a[0], priority, lambda x, y: x >= y)
(l, res) = (1, 1)
for i in range(1, n):
	first[a[i] - 1].popleft()
	if not first[a[i] - 1]:
		priority = float('inf')
	else:
		priority = first[a[i] - 1][0]
	if not treap.find(a[i]):
		if l == k:
			treap = treap.delete(treap.key)
			l -= 1
		if treap is not None:
			treap = treap.insert(Treap(a[i], priority, lambda x, y: x >= y))
		else:
			treap = Treap(a[i], priority, lambda x, y: x >= y)
		l += 1
		res += 1
	else:
		treap = treap.delete(a[i])
		if treap is not None:
			treap = treap.insert(Treap(a[i], priority, lambda x, y: x >= y))
		else:
			treap = Treap(a[i], priority, lambda x, y: x >= y)
print(res)


R = lambda : map(int, input().split())
stack = []
(n, k) = R()
l = list(R())
(curr, tot) = (0, 0)
for i in range(n):
	if l[i] not in stack:
		if curr < k:
			curr = curr + 1
		else:
			(c, z) = (0, -1)
			for j in range(k):
				if stack[j] not in l[i:]:
					z = j
					break
				else:
					c = max(c, i + l[i:].index(stack[j]))
			stack.pop(z) if z != -1 else stack.remove(l[c])
		stack.insert(0, l[i])
		tot += 1
print(tot)


import sys
from bisect import bisect
from collections import Counter, defaultdict
l1 = sys.stdin.readline()
l2 = sys.stdin.readline()
(n, k) = map(int, l1.split(' '))
books = list(map(int, l2.split(' ')))
cost = 0
cache = set()
x = defaultdict(list)
for (i, book_id) in enumerate(books):
	x[book_id].append(i)
for (i, book_id) in enumerate(books):
	if book_id in cache:
		continue
	if len(cache) < k:
		cache.add(book_id)
		cost += 1
		continue
	min_next_closest = i
	to_evict = next(iter(cache))
	for x_id in cache:
		indices = x[x_id]
		index = bisect(indices, i)
		if index == len(indices):
			to_evict = x_id
			break
		next_closect = indices[index]
		if next_closect > min_next_closest:
			min_next_closest = next_closect
			to_evict = x_id
	cache.remove(to_evict)
	cache.add(book_id)
	cost += 1
print(cost)