Вступ до університету#10672

Вступ до університету

0,5 секунди

64 мегабайти

Дуже легка

Амін і Азіз успішно пройшли технічний етап вступу до корейського університету KAIST. Разом із ними цей етап подолали всього $n$ кандидатів. Однак це ще не гарантує їхнього зарахування. На наступному етапі університет обиратиме студентів, керуючись їхніми соціальними якостями. Соціальну якість $i$ -го кандидата позначимо як $s_{i}$ s_i.

Університет проводить відбір за параметром, який називається діапазоном відбору, що позначається як $d$ . Мета — обрати найбільшу можливу групу кандидатів, у якій різниця між максимальним та мінімальним соціальними якостями не перевищує $d$ . Це забезпечує оптимальну взаємодію у студентському середовищі. Визначте максимальну кількість студентів, яку може прийняти університет за цієї умови.

Вхідні дані

У першому рядку міститься два цілих числа $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \leq n \leq 10^{5}) і $d$ ( $0 \leq d \leq 1 0^{9}$ 0 \leq d \leq 10^{9}) — кількість кандидатів і діапазон відбору.

У другому рядку міститься $n$ цілих чисел $s_{1}, s_{2}, \dots, s_{n}$ s_1,s_2,\dots,s_n ( $- 1 0^{9} \leq s_{i} \leq 1 0^{9}$ -10^{9} \leq s_i \leq 10^{9}) — соціальні якості кандидатів.

Вихідні дані

В єдиному рядку вкажіть максимальну кількість студентів, яку університет може прийняти.

Приклади

Приклад 1

Примітка

Університет може прийняти максимум $3$ студентів, наприклад, ${1, 3, 4}$ \{1, 3, 4\} або ${2, 3, 5}$ \{2, 3, 5\}. В обох групах різниця між найбільш і найменш соціальним кандидатом не перевищує $d = 3$ d=3.

Оцінювання

Завдання складається з наступних 4 підзадач: