Распределение пряности
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Известный Ментат основал университет изучения вселенной Дюны и теперь распределяет ресурс пряности между своими подопечными. Всего ему предстоит распределить $$$n$$$ единиц пряности, каждая из которых предназначена для исследований в области направления номер $$$a_i$$$.

По правилам, установленным императором, одному обучаемому нельзя выделить две единицы пряности для изучений по совпадающим или похожим направлениям. Направления с номерами $$$a_i$$$ и $$$a_j$$$ считаются похожими, если разница между их номерами не превышает $$$k$$$, то есть если $$$|a_i - a_j| \le k$$$.

Пряность — ценнейшее и редчайшее вещество во вселенной, которое способно ускорить человеческий мозг до уровня суперкомпьютера, поэтому Ментат упорядочил студентов по их способностям и хочет распределить пряность между как можно меньшим количеством наиболее способных студентов. Например, пряность для изучения направлений $$$1$$$, $$$2$$$ и $$$4$$$ при $$$k = 2$$$ можно выдать двум студентам (первому — $$$1$$$ и $$$4$$$, второму — $$$2$$$), но нельзя выдать все одному студенту, потому что направления $$$1$$$ и $$$2$$$ похожи.

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

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

В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$k$$$ — количество единиц пряности и число, задающее, какие направления изучения вселенной считаются похожими ($$$1 \le n \le 2 \cdot 10^5$$$; $$$0 \le k \le 10^9$$$).

Во второй строке через пробел перечислены $$$n$$$ чисел $$$a_i$$$ — направления, для изучения которых нужна пряность ($$$1 \le a_i \le 10^9$$$).

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

Выведите единственное целое число — минимальное количество студентов, по которым можно распределить весь объем пряности.

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.

ПодзадачаБаллыДоп. ограничения Необходимые подзадачи Информация о проверке
0примеры из условияполная
17$$$n \le 3$$$полная
213$$$k = 0$$$полная
315$$$n \le 9$$$0, 1первая ошибка
418$$$n \le 1000$$$, $$$1 \le k \le 2$$$, все $$$a_i$$$ различныпервая ошибка
522$$$n \le 1000$$$0, 1, 3, 4первая ошибка
625нет1 – 5первая ошибка

Примеры

Входные данные
3 2
1 2 4
Выходные данные
2
Входные данные
9 2
7 1 2 8 5 4 9 3 6
Выходные данные
3
Входные данные
3 0
3 1 1
Выходные данные
2
Входные данные
4 4
1 100 77 32
Выходные данные
1

Примечание

Пояснения к первому примеру даны в условии.

Во втором примере к условию достаточно выдать каждому из трех студентов единицы пряности с одинаковым остатком по модулю $$$3$$$. Двух студентов недостаточно, потому что никакие две из единиц пряности по направлениям $$$1$$$, $$$2$$$ и $$$3$$$ не могут достаться одному студенту.

В третьем примере к условию две единицы пряности по одному и тому же направлению $$$1$$$ должны быть отданы разным студентам, тогда как единицу пряности по направлению $$$3$$$ можно будет после отдать любому из них.

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