Автор: | М. Спорышев, И. Блинов | Ограничение времени: | 2 сек | |
Входной файл: | input.txt | Ограничение памяти: | 512 Мб | |
Выходной файл: | output.txt | |||
Максимальный балл: | 100 |
Инженер Антон зашёл в магазин радиодеталей. В магазине ровно 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 |
|
|