E. Массив Монокарпа
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Монокарпа есть массив $$$a$$$, состоящий из $$$n$$$ целых элементов, причем $$$i$$$-й элемент массива равен $$$a_i$$$.

Монокарп хочет, чтобы разность между максимальным и минимальным элементами в его массиве не превышала целого числа $$$d$$$.

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

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

Перед вами стоит задача помочь Монокарпу и определить минимальное количество подряд идущих элементов, которые необходимо удалить из его массива.

Входные данные

В первой строке следуют два целых числа $$$n$$$ и $$$d$$$ ($$$2 \le n \le 200\,000$$$, $$$1 \le d \le 10^{9}$$$) — количество элементов в массиве Монокарпа и максимально допустимая разность между максимальным и минимальным элементами массива.

Во второй строке следует последовательность целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$), причем $$$i$$$-й элемент последовательности равен $$$i$$$-му элементу массива Монокарпа.

Выходные данные

Выведите минимальное количество подряд идущих элементов массива Монокарпа, которые нужно удалить таким образом, чтобы разность между максимальным и минимальным элементами в массиве Монокарпа после удаления элементов не превышала целого числа $$$d$$$.

Примеры
Входные данные
6 3
3 3 1 8 5 4
Выходные данные
2
Входные данные
7 10
15 12 18 13 12 11 16
Выходные данные
0
Примечание

В первом примере нужно удалить два подряд идущих элемента в позициях $$$4$$$ и $$$5$$$. После этого массив станет равным $$$[3, 3, 1, 4]$$$. Разность между максимальным и минимальным элементами в этом массиве равна $$$4 - 1 = 3$$$. Так как $$$d = 3$$$, этот массив является подходящим.

Во втором примере не нужно удалять ни одного элемента, так как разность между максимальным и минимальным элементами в этом массиве равна $$$18 - 11 = 7$$$. Так как $$$d = 10$$$, этот массив является подходящим.