B. Хайди и Библиотека (средняя)
ограничение по времени на тест
10 секунд
ограничение по памяти на тест
256 мегабайт
ввод
stdin
вывод
stdout

В то время как люди сегодня читают все меньше книг на бумаге, аудитория читателей среди сурков выросла. Хайди расширила хранилище библиотеки и теперь может обслуживать большее количество посетителей.

Входные данные

Входные данные те же, что и в простой версии задачи, но увеличены ограничения: 1 ≤ n, k ≤ 400 000.

Выходные данные

Выходные данные те же, что и в простой версии задачи.

Примеры
Входные данные
4 100
1 2 2 1
Выходные данные
2
Входные данные
4 1
1 2 2 1
Выходные данные
3
Входные данные
4 2
1 2 3 1
Выходные данные
3