Ваши поиски Хайди закончились – вы наконец-то нашли ее в библиотеке, и одета она была как человек. На самом деле Хайди уже очень много времени находилась там!

В её обязанности входит покупать и хранить книги в библиотеке, чтобы люди могли их брать и читать. Всего существует n различных книг, пронумерованных от 1 до n.

Рассмотрим работу библиотеки в течение n следующих дней. Хайди знает заранее, что в i-й день (1 ≤ i ≤ n) ровно один человек придет в библиотеку, захочет взять книгу номер a_i, прочитает ее за несколько часов и вернет ее обратно в тот же день.

Хайди хочет удовлетворить всех своих посетителей, поэтому она должна быть уверена, что книга a_i всегда есть в наличии в библиотеке в i-й день. Ночью (перед началом i-го дня) она может пойти в книжный магазин (который работает по ночам, чтобы избежать конкуренции с библиотекой) и купить любую книгу. Каждая из книг стоит 1 CHF. Конечно, если у нее в библиотеке уже есть книга нужная книга, Хайди не нужно покупать её ещё раз. Изначально в библиотеке нет ни одной книги.

Библиотека устроена таким образом, что размер хранилища библиотеки составляет k, другими словами в любой момент времени в библиотеке может находиться не более чем k книг. Если после покупки новой книги в библиотеке станет более, чем k книг, Хайди должна сначала избавиться от какой-нибудь уже имеющейся книги, чтобы освободить место для новой. Если позже ей понадобится книга, от которой она избавилась, ей нужно будет купить эту книгу снова.

Вам задано k и последовательность запросов посетителей на книги — a₁, a₂, ..., a_n. Перед вами стоит задача определить минимальную сумму (в CHF), которую Хайди нужно потратить, чтобы удовлетворить запросы всех посетителей.