隧道灯
测试数据来自 system/1755
时间限制:1秒 内存限制:256M
【题目描述】
高速路上一般都有很多隧道,为行车安全,隧道中灯要一直亮着。
但是为了节约,一般隧道中的灯都没有必要全部点亮,在保证照明的情况下,需要关掉尽量多的灯。具体来说,设隧道中有 \(n\) 盏灯以及每盏灯的位置 \(p_i\)(距离隧道一侧入口的距离),\(p_i\) 均不相等,当某两盏灯的距离小于 \(D\) 时,那么在这两盏灯之间的灯就可以关掉(即若第 \(i-1\) 盏与第 \(i+1\) 盏的距离小于等于 \(D\),则可以关掉第 \(i\) 盏)。
现在给出一个隧道中灯的为止信息和照明参数 \(D\),求在保证洞里的光线是充足的情况下,最多可以关掉多少盏灯?
注意:距离一侧入口最近和最远的两盏灯必须是亮着。
【输入格式】
第一行两个数,\(N\) 和 \(D\),表示有隧道中有 \(N\) 盏灯,照明距离参数为 \(D\)。
接下来的 \(N\) 行,每行一个整数 \(p_i\),表示每盏灯的位置。
【输出格式】
一个数,能关掉灯的最大数目。
【输入输出样例】
Input
3 3
1
2
3
Output
1
【数据限制】
对于 \(100\%\) 的数据,\(1<N<100000\),\(1 ≤ D,p_i ≤ 10^9\)。
【来源】
Mr.he