Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:1024 MB
Statistics

小S排座位

题目描述

​ 作为学校违纪行为的代言人,小S被老师安排去排一个新班级的座位。新班级有 $n$ 位同学,他们的成绩按顺序分别为 $a_1,a_2,\dots,a_n$($a_i\leq a_{i+1}$)。教室的一桌会坐相邻的两个人,称为同桌。为促进互帮互助,一对同桌的成绩之差的绝对值必须大于等于给定的常数 $K$,但这样会导致一些同学没有同桌,而没有同桌的人会去暴D小S。小S不想被D,所以请你求出他最多能排出几对同桌。

输入格式

​ 第一行输入两个整数 $n,K$,含义见题目描述。

​ 第二行输入 $n$ 个整数 $a_i$,保证数组 $a$ 不降。

输出格式

​ 第一行一个整数 $ans$ ,表示答案。

样例一

input

5 1
1 2 3 4 5

output

2

样例二

input

8 5
1 4 5 6 8 9 10 15

output

4

限制与约定

​ 对于$100\%$的数据,保证$1\le n\leq 10^6,0\leq a_i,K\leq 10^9$

子任务编号 分值 $n\leq$ $a_i,K\le$ 特殊性质
$1$ 5 $2$ $10^9$
$2$ 15 $100$ $10^9$
$3$ 15 $10^6$ $100$
$4$ 15 $10^6$ $10^9$ 保证 $a_i=i$
$5$ 15 $10^6$ $10^9$ 保证 $K>\dfrac{a_n}{2}$
$6$ 35 $10^6$ $10^9$