Вы являетесь автором раунда Codeforces и подготовили \(n\) задач, которые вы собираетесь задать, причем задача \(i\) имеет сложность \(a_i\). Вы будете выполнять следующий процесс:
- удалить некоторые (возможно, ноль) задач из списка;
- переставить оставшиеся задачи в любом порядке, который вы пожелаете.
Раунд считается сбалансированным, если и только если абсолютная разница между сложностью любых двух последовательных задач не превышает \(k\) (то есть меньше или равен \(k\)).
Какое минимальное количество задач нужно удалить, чтобы расстановка задач была сбалансированной?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество задач, которые нужно удалить, чтобы расстановка задач была сбалансированной.
Примечание
В первом примере мы можем удалить первые \(2\) задачи и составить набор, используя задачи со сложностями \([4, 5, 6]\), с разницей между соседними задачами равной \(|5 - 4| = 1 \leq 1\) и \(|6 - 5| = 1 \leq 1\).
Во втором примере мы можем взять одну задачу и составить раунд, используя задачу со сложностью \(10\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
5 1
1 2 4 5 6
1 2
10
8 3
17 3 1 20 12 5 17 12
4 2
2 4 6 8
5 3
2 3 19 10 8
3 4
1 10 5
8 1
8 3 1 4 5 10 7 3
|
2
0
5
0
3
1
4
|