| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
| Максимальный балл: | 100 |
Автономный необитаемый подводный аппарат проплыл по заданной траектории, записав последовательность целых чисел ai — глубину своего погружения в метрах на i-й секунде.
Известно, что за одну секунду глубина погружения не может измениться более чем на d метров в большую или меньшую сторону. Определение глубины не всегда работает точно, из-за чего это условие может быть нарушено в исходной последовательности. Необходимо очистить данные, удалив из них как можно меньше элементов.
Требуется написать программу, которая по данным ai и d определит наименьшее возможное количество элементов, которые нужно удалить из последовательности ai чтобы разность рядом стоящих элементов в оставшейся последовательности по модулю не превосходила d.
Входные данные содержат целые числа n и d — количество измерений и максимальный перепад глубины. Далее следует n целых чисел ai — измерения глубины.
Выходные данные должны содержать единственное целое число — наименьшее количество удаляемых элементов.
1 ≤ n ≤ 20 000, 0 ≤ d ≤ 1000, 0 ≤ ai ≤ 109
| № | Стандартный вход | Стандартный выход |
|---|---|---|
| 1 | |
|