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: interview

Starter code:

Solutions:
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)


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) # i min == 0
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)

R=lambda:list(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)


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
	# print("To evict %s" % to_evict)
	cache.remove(to_evict)
	cache.add(book_id)
	cost += 1

print(cost)

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
        else:
            if 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([i for i in range(n) if books[i]])

    print(cost)

def __starting_point():
    solve()
__starting_point()

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)

from collections import deque


class Treap():  # self.priority_comparator(root.priority, descendant.priority) == True
    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):  # self a.k.a. left <= right ========= tested
        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):                   # tested
        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):     # tested
        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):        # UN!tested
        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)

n,k=list(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)


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


(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(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:
        #print(item, req_list)
        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(bucket, req_list)

#print(req_list)
print(cost)

n,k=list(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)





# Made By Mostafa_Khaled


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 = list(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())) + [-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)