Условие:
Програмистка Лина решила сменить свою профессию и образ жизни. Без долгих раздумий Лина переехала в Париж и устроилось на работу посудомойкой в маленьком ресторане. Чтобы получать больше удовольствия во время перерывов Лина принесла кофейник.
В течение обеда Лине передают грязные тарелки через маленькое окошко. В ресторане всего K различных видов тарелок, и Лина их складывает в K стопок. Когда Лина получает новую тарелку, она ее моет, затем быстро сушит, и после этого в зависимости от размера тарелки кладёт её в соответствующую стопку.
Поскольку в ресторанчике мало комнат, Лина держит кофейник в этой же комнате на вершине одной из стопок. Если Лина хочет поставить тарелку на стопку, где стоит кофейник, ей приходиться перемещать его на другую стопку.
Лина не может перестать думать о том, что зная порядок поступления тарелок, она могла переставлять кофейник реже. Требуется найти наименьшее количество перестановок кофейника, если и изначально он мог находиться на любой стопке.
Входные данные Первая строка содержит два натуральных числа: количество тарелок N ≤ 106 и количество стопок K ≤ 109. Следующие N строк содержат по одному целому числу 1 ≤ ai ≤ K – номер стопки на которую должна быть поставлена i-ая тарелка.
Выходные данные Выведите одно число, минимально возможное количество перестановок кофейника.
