C. Стабильные параллели
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Паша и Тёма приехали преподавать в зимний ноутбучный университет. Теперь им необходимо разобраться с учениками.

Есть $$$n$$$ учеников, пронумерованных от $$$1$$$ до $$$n$$$. Уровень знаний $$$i$$$-го ученика равен $$$a_i$$$. Всех учеников нужно распределить на стабильные параллели. Параллель называется стабильной, если после сортировки всех учеников параллели в порядке возрастания их уровня знаний у любых двух подряд идущих учеников разница уровня знаний не превосходит $$$x$$$.

Преподаватели достаточно находчивые люди, поэтому они могут пригласить не более $$$k$$$ дополнительных учеников с любым требуемым уровнем знаний. Определите минимальное число стабильных параллелей, на которые можно распределить всех учеников (возможно, пригласив не более $$$k$$$ новых учеников).

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

В первой строке вводятся три целых числа $$$n$$$, $$$k$$$, $$$x$$$ ($$$1 \le n \le 200\,000, 0 \le k \le 10^{18}, 1 \le x \le 10^{18}$$$) — количество учеников, сколько учеников можно пригласить дополнительно и максимальная допустимая разница уровня знаний.

Во второй строке вводится $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$) — уровни знаний учеников.

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

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

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

В данной задаче $$$50$$$ тестов, помимо тестов из условия, каждый из них оценивается в $$$2$$$ балла. Результаты проверки ваших решений на всех тестах будут доступны сразу во время соревнования.

Решения, корректно работающие при $$$n, k, x, a_i \le 10$$$, наберут не менее $$$20$$$ баллов.

Решения, корректно работающие при $$$k = 0$$$, наберут не менее $$$14$$$ баллов.

Решения, корректно работающие, когда ответ не превосходит $$$2$$$, наберут не менее $$$16$$$ баллов.

Решения, корректно работающие при $$$n, k, x, a_i \le 1000$$$, наберут не менее $$$40$$$ баллов.

Примеры
Входные данные
8 2 3
1 1 5 8 12 13 20 22
Выходные данные
2
Входные данные
13 0 37
20 20 80 70 70 70 420 5 1 5 1 60 90
Выходные данные
3
Примечание

В первом примере из условия можно пригласить учеников с уровнями знаний, равными $$$2$$$ и $$$11$$$. Тогда учеников можно разделить на следующие стабильные параллели:

  1. $$$[1, 1, 2, 5, 8, 11, 12, 13]$$$,
  2. $$$[20, 22]$$$.

Во втором примере из условия новых учеников приглашать нельзя, поэтому потребуется $$$3$$$ параллели:

  1. $$$[1, 1, 5, 5, 20, 20]$$$
  2. $$$[60, 70, 70, 70, 80, 90]$$$
  3. $$$[420]$$$