Известный Ментат основал университет изучения вселенной Дюны и теперь распределяет ресурс пряности между своими подопечными. Всего ему предстоит распределить $$$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 | – | примеры из условия | полная | |
1 | 7 | $$$n \le 3$$$ | полная | |
2 | 13 | $$$k = 0$$$ | полная | |
3 | 15 | $$$n \le 9$$$ | 0, 1 | первая ошибка |
4 | 18 | $$$n \le 1000$$$, $$$1 \le k \le 2$$$, все $$$a_i$$$ различны | первая ошибка | |
5 | 22 | $$$n \le 1000$$$ | 0, 1, 3, 4 | первая ошибка |
6 | 25 | нет | 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$$$ можно будет после отдать любому из них.
В четвертом примере к условию все единицы пряности могут быть выданы одному студенту, и правила императора не будут нарушены.