Задача №112782. Кофейник
Програмистка Лина решила сменить свою профессию и образ жизни. Без долгих раздумий Лина переехала в Париж и устроилось на работу посудомойкой в маленьком ресторане. Чтобы получать больше удовольствия во время перерывов Лина принесла кофейник.
В течение обеда Лине передают грязные тарелки через маленькое окошко. В ресторане всего K различных видов тарелок, и Лина их складывает в K стопок. Когда Лина получает новую тарелку, она ее моет, затем быстро сушит, и после этого в зависимости от размера тарелки кладёт её в соответствующую стопку.
Поскольку в ресторанчике мало комнат, Лина держит кофейник в этой же комнате на вершине одной из стопок. Если Лина хочет поставить тарелку на стопку, где стоит кофейник, ей приходиться перемещать его на другую стопку.
Лина не может перестать думать о том, что зная порядок поступления тарелок, она могла переставлять кофейник реже. Требуется найти наименьшее количество перестановок кофейника, если и изначально он мог находиться на любой стопке.
Первая строка содержит два натуральных числа: количество тарелок N ≤ 106 и количество стопок K ≤ 109. Следующие N строк содержат по одному целому числу 1 ≤ ai ≤ K – номер стопки на которую должна быть поставлена i-ая тарелка.
Выведите одно число, минимально возможное количество перестановок кофейника.
8 3
3
1
2
1
1
3
3
2
2
Подзадача 1.
N, K ≤ 10. Решение оценивается в 10 баллов.
Подзадача 2.
N, K ≤ 1000. Решение оценивается в 20 баллов.
Подзадача 3.
K = 2. Решение оценивается в 20 баллов.
Подзадача 4.
Дополнительные ограничения отсутствуют. Решение оценивается в 50 баллов.