Паша и Тёма приехали преподавать в зимний ноутбучный университет. Теперь им необходимо разобраться с учениками.
Есть $$$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$$$. Тогда учеников можно разделить на следующие стабильные параллели:
Во втором примере из условия новых учеников приглашать нельзя, поэтому потребуется $$$3$$$ параллели:
