Есть \(n\) учеников, пронумерованных от \(1\) до \(n\). Уровень знаний \(i\)-го ученика равен \(a_i\). Всех учеников нужно распределить на стабильные группы. Группа называется стабильной, если после сортировки всех учеников группы в порядке возрастания их уровня знаний у любых двух подряд идущих учеников разница уровня знаний не превосходит \(x\).
Например, при \(x = 4\) группа с уровнями знаний \([1, 10, 8, 4, 4]\) является стабильной (потому что \(4 - 1 \le x\), \(4 - 4 \le x\), \(8 - 4 \le x\), \(10 - 8 \le x\)), а группа с уровнями \([2, 10, 10, 7]\) не является стабильной (\(7 - 2 = 5 > x\)).
Преподаватели — достаточно находчивые люди, поэтому в дополнение к \(n\) имеющимся ученикам они могут пригласить не более \(k\) дополнительных учеников с любым уровнем знаний на выбор преподавателей. Определите минимальное число стабильных групп, на которые можно распределить всех учеников (возможно, пригласив новых учеников).
Например, если есть два ученика с уровнями знаний \(1\) и \(5\), \(x = 2\), и \(k \ge 1\), то можно пригласить ученика с уровнем знаний \(3\) и определить всех учеников в одну стабильную группу.
Примечание
В первом примере из условия можно пригласить учеников с уровнями знаний, равными \(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]\)