{"raw_statement":[{"iden":"statement","content":"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_.\n\nWe 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.\n\nHeidi 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.\n\nThere 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.\n\nYou 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?"},{"iden":"input","content":"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."},{"iden":"output","content":"On a single line print the minimum cost of buying books at the store so as to satisfy all requests."},{"iden":"examples","content":"Input\n\n4 80\n1 2 2 1\n\nOutput\n\n2\n\nInput\n\n4 1\n1 2 2 1\n\nOutput\n\n3\n\nInput\n\n4 2\n1 2 3 1\n\nOutput\n\n3"},{"iden":"note","content":"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.\n\nIn 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.\n\nIn 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."}],"translated_statement":[{"iden":"statement","content":"你对海蒂的寻找结束了——你终于在图书馆找到了她，她打扮成了一名人类。事实上，她在那里度过了如此多的时间，以至于现在她成了图书馆的管理者！她的工作是购买书籍并将其保留在图书馆中，以便人们可以借阅和阅读。共有 #cf_span[n] 本不同的书，编号为 #cf_span[1] 到 #cf_span[n]。\n\n我们将考察图书馆在 #cf_span[n] 个连续天内的运作情况。海蒂提前知道，在第 #cf_span[i] 天（#cf_span[1 ≤ i ≤ n]），恰好有一人前来图书馆，请求借阅书 #cf_span[ai]，数小时后阅读完毕，并于当天晚些时候归还。\n\n海蒂非常希望取悦每一位客人，因此她会确保在第 #cf_span[i] 天始终拥有书 #cf_span[ai]。在第 #cf_span[i] 天的前一晚，她可以选择去书店（书店在夜间营业以避免与图书馆竞争）购买任何一本书，价格为 1 CHF。当然，如果她已经拥有某本书，则无需再次购买。最初，图书馆没有任何书籍。\n\n但存在一个问题：图书馆的容量为 #cf_span[k]——这意味着任何时候图书馆中最多只能存放 #cf_span[k] 本书。如果购买一本新书会导致海蒂拥有的书籍超过 #cf_span[k] 本，她必须先移除一本她已有的书，以腾出空间给新书。如果她之后需要一本已被移除的书，她必须重新购买。\n\n给你 #cf_span[k] 和书的请求序列 #cf_span[a1, a2, ..., an]。满足所有请求所需的最小购买成本（以 CHF 计）是多少？\n\n输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 80]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n]）——书的请求序列。\n\n请在一行中输出满足所有请求所需购买书籍的最小成本。\n\n在第一个测试用例中，海蒂可以永久保留所有书籍。因此，她只需要在第一天之前购买书 #cf_span[1]，在第二天之前购买书 #cf_span[2]。\n\n在第二个测试用例中，她一次只能保留一本书。因此她需要在第一天、第二天和第四天购买新书。\n\n在第三个测试用例中，在第三天购买书 #cf_span[3] 之前，她必须决定移除书 #cf_span[1] 还是书 #cf_span[2]。当然，她应当保留书 #cf_span[1]，因为第四天会再次需要它。"},{"iden":"input","content":"输入的第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n, k ≤ 80]）。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ n]）——书的请求序列。"},{"iden":"output","content":"请在一行中输出满足所有请求所需购买书籍的最小成本。"},{"iden":"examples","content":"输入4 801 2 2 1输出2输入4 11 2 2 1输出3输入4 21 2 3 1输出3"},{"iden":"note","content":"在第一个测试用例中，海蒂可以永久保留所有书籍。因此，她只需要在第一天之前购买书 #cf_span[1]，在第二天之前购买书 #cf_span[2]。在第二个测试用例中，她一次只能保留一本书。因此她需要在第一天、第二天和第四天购买新书。在第三个测试用例中，在第三天购买书 #cf_span[3] 之前，她必须决定移除书 #cf_span[1] 还是书 #cf_span[2]。当然，她应当保留书 #cf_span[1]，因为第四天会再次需要它。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions:**\n\n- Let $ n $ be the number of days and the number of distinct books.\n- Let $ k $ be the library capacity (maximum number of books that can be stored at any time).\n- Let $ a = [a_1, a_2, \\dots, a_n] $ be the sequence of book requests, where $ a_i \\in \\{1, 2, \\dots, n\\} $ is the book requested on day $ i $.\n- Initially, the library contains no books.\n- On the night before day $ i $, Heidi may purchase any book for 1 CHF.\n- If purchasing a new book would exceed capacity $ k $, she must remove one existing book.\n- Goal: Minimize the total number of book purchases.\n\n**Constraints:**\n\n- At any time, the number of books in the library $ \\leq k $.\n- On day $ i $, book $ a_i $ must be present in the library.\n- A book is available if it has been purchased and not yet removed.\n\n**Objective:**\n\nMinimize the number of purchases (i.e., the number of times a book is bought when not already in the library).\n\n**Formal Problem Statement:**\n\nGiven integers $ n, k $ and a sequence $ a = (a_1, \\dots, a_n) $, determine the minimum number of purchases required to ensure that for each $ i \\in \\{1, \\dots, n\\} $, book $ a_i $ is present in the library on day $ i $, under the constraint that the library never contains more than $ k $ books at once, and books may be removed at any time before a purchase if necessary.\n\nThis is equivalent to the **optimal offline caching problem** (also known as the **Belady’s algorithm**), where the goal is to minimize page faults (purchases) by evicting the book that will be used the farthest in the future (or never again) when the cache is full.\n\nThus, the problem reduces to:\n\n> Compute the minimum number of purchases under the optimal eviction strategy (Belady’s algorithm) for a cache of size $ k $, given a request sequence $ a_1, \\dots, a_n $, starting from an empty cache.\n\n**Mathematical Formulation:**\n\nLet $ C \\subseteq \\{1, \\dots, n\\} $ be the set of books currently in the library, with $ |C| \\leq k $.  \nInitialize $ C = \\emptyset $, cost $ = 0 $.  \nFor each day $ i = 1 $ to $ n $:\n\n- If $ a_i \\notin C $:\n  - Increment cost by 1.\n  - If $ |C| < k $: add $ a_i $ to $ C $.\n  - Else: remove from $ C $ the book $ b \\in C $ that is requested the farthest in the future (or never again), then add $ a_i $ to $ C $.\n\n**Output:** The final value of cost.\n\nThis is the **minimum cost** (in CHF).","simple_statement":null,"has_page_source":false}