| Автор: | М. Спорышев, И. Блинов | Ограничение времени: | 2 сек | |
| Входной файл: | input.txt | Ограничение памяти: | 512 Мб | |
| Выходной файл: | output.txt |
Инженер Антон зашёл в магазин радиодеталей. В магазине ровно N стеллажей. На i-м стеллаже лежат радиодетали типа ai (на двух различных стеллажах тип радиодеталей может повторяться). Антон обходит с тележкой стеллажи в порядке от первого до N-го.
Когда Антон подходит к очередному стеллажу, он смотрит в тележку. Если в тележке нет радиодеталей такого типа, как на стеллаже, Антон берёт деталь со стеллажа и складывает в тележку. Если радиодеталь такого типа в тележке уже лежит, Антон просто идет дальше.
К сожалению, вместимость тележки ограничена K деталями. Поэтому, если тележка заполнена, а Антону необходимо выбрать, какую из имеющихся в тележке радиодеталей нужно убрать, прежде чем складывать новую деталь.Антон знает заранее, какие типы радиодеталей лежат на стеллажах, и хочет каждый раз выбрасывать из тележки такую деталь, чтобы как можно меньше раз складывать новые радиодетали в тележку (складывает он их только в случае, если таких деталей в тележке нет на данный момент).
Помогите Антону узнать, какое минимальное количество раз ему придётся складывать новую деталь в тележку.
Рекомендуется рассмотреть частичные решения для N ≤ 1000, ai ≤ 105.
Входной файл содержит целое число два целых числа N и K, вторая строка содержит N чисел ai.
Выходной файл должен содержать единственное число — минимальное количество раз, которое придётся положить деталь в тележку.
1 ≤ N, K ≤ 105
0 ≤ ai ≤ 109
| № | Входной файл (input.txt) |
Выходной файл (output.txt) |
|---|---|---|
| 1 | |
|
| 2 | |
|
| 3 | |
|