Задача A. Перепад глубины ≡

Условие

Автономный необитаемый подводный аппарат проплыл по заданной траектории, записав последовательность целых чисел a_i — глубину своего погружения в метрах на i-й секунде.

Известно, что за одну секунду глубина погружения не может измениться более чем на d метров в большую или меньшую сторону. Определение глубины не всегда работает точно, из-за чего это условие может быть нарушено в исходной последовательности. Необходимо очистить данные, удалив из них как можно меньше элементов.

Требуется написать программу, которая по данным a_i и d определит наименьшее возможное количество элементов, которые нужно удалить из последовательности a_i чтобы разность рядом стоящих элементов в оставшейся последовательности по модулю не превосходила d.

Формат входных данных

Входные данные содержат целые числа n и d — количество измерений и максимальный перепад глубины. Далее следует n целых чисел a_i — измерения глубины.

Формат выходных данных

Выходные данные должны содержать единственное целое число — наименьшее количество удаляемых элементов.

Ограничения

1 ≤ n ≤ 20 000, 0 ≤ d ≤ 1000, 0 ≤ a_i ≤ 10⁹

Примеры тестов

3 4
10 15 14

1

Разбор

Задача решается методом динамического программирования.

Пусть dp_i — минимальное количество элементов, которые нужно удалить, чтобы элементы на префиксе с 1-го по i-й имели перепад не более d, и при этом элемент i остался в последовательности.

Тогда dp₁ = 0 и dp_i = minj = 1,i − 1dp_j + i − j − 1, i = 2,n.

Следует также учесть возможность удаления элементов в суффиксе последовательности, поэтому окончательный ответ равен mini = 1,ndp_i + n − i.