Наши тесты не готовы. Впереди крупная олимпиада. Но ведь самая главная цель авторов контеста — сделать еще одну задачу.
Назовём диаметром мультимножества точек на прямой максимальное расстояние между двумя точками этого множества. Например, диаметр мультимножества {1, 3, 2, 1} равен 2.
Диаметр мультимножества, состоящего из одной точки, равен 0.
Даны n точек на прямой. Какое минимальное число точек необходимо убрать, чтобы диаметр мультимножества оставшихся точек не превосходил d?
Выходные данные
Выведите одно целое число — минимальное количество удалённых точек.
Примечание
В первом тестовом примере выгодно удалить точку с координатой 4. Оставшиеся точки будут иметь координаты 1 и 2, поэтому диаметр оставшегося мультимножества будет равен 2 - 1 = 1.
Во втором тестовом примере диаметр равен 0, поэтому удалять точки не потребуется.
В третьем тестовом примере выгодно удалить точки с координатами 1, 9 и 10. Оставшиеся точки будут иметь координаты 3, 4 и 6, поэтому диаметр будет равен 6 - 3 = 3.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 1
2 1 4
|
1
|
|
2
|
3 0
7 7 7
|
0
|
|
3
|
6 3
1 3 4 6 9 10
|
3
|