Небоскрёбы
Небоскрёбы
Спустя 5000 лет, когда эпидемия коронавируса была остановлена, в Баку планируется построить n небоскрёбов. Баку будем представлять как координатную ось чисел. Для каждого небоскрёба даны его координата (xi
) на координатной оси и высота (hi
). Инженеры считают небоскрёб "невыгодным" в том случае, если слева от него на расстоянии не больше d, а также справа от него на расстоянии не больше d, расположен небоскрёб, высота которого по крайней мере в два раза больше высоты данного небоскрёба (этот небоскрёб сам может быть невыгодным). Такие небоскрёбы считаются неуспешными с точки зрения бизнеса, поэтому инженеры планируют построить вместо них какой-нибудь другой объект. Вы должны посчитать количество "невыгодных" небоскрёбов, чтобы инженеры знали своё дело.
Входные данные
В первой строке даны два числа n (1 ≤ n ≤ 105
) и d (1
≤ d ≤ 109
). В следующих d строках даны числа xi
и hi
(1 ≤ xi
, hi
≤ 109
). Все координаты небоскрёбов различны.
Выходные данные
Выведите количество невыгодных небоскрёбов.
6 4 10 3 6 2 5 3 9 7 3 6 11 2
2