Паша и Тёма приехали преподавать в зимний ноутбучный университет. Теперь им необходимо разобраться с учениками.
Есть \(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}\)) — уровни знаний учеников.
Формат выходных данных
В единственной строке выведите одно число — искомое минимальное число стабильных параллелей, на которое можно разбить учеников.
Примечание
В первом примере из условия можно пригласить учеников с уровнями знаний, равными \(2\) и \(11\). Тогда учеников можно разделить на следующие стабильные параллели:
-
\([1, 1, 2, 5, 8, 11, 12, 13]\),
-
\([20, 22]\).
Во втором примере из условия новых учеников приглашать нельзя, поэтому потребуется \(3\) параллели:
-
\([1, 1, 5, 5, 20, 20]\)
-
\([60, 70, 70, 70, 80, 90]\)
-
\([420]\)