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

Входной файл:Стандартный вход   Ограничение времени: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
3 4
10 15 14
1

0.121s 0.024s 15