已知 n 盏灯以及每盏灯的位置 p_i , p_i 均不相等,当两盏灯之间的距离小于 dist 时,若这个安全距离里面还有灯是亮着时,就可以关掉这些灯(即若第 i-1 盏与第 i+1 盏的距离 \leq dist ,则可以关掉第 i 盏)。
求在保证洞里的光线是充足的情况下,一段区域里能删除的灯的最大值。
距离洞口最近和最远的两盏灯必须是亮着。
第一行两个数, n 和 dist 。
第二行 n 个数,即每盏灯的位置 p_i 。
一个数,即一段区域里能删除的灯的最大值。
3 3 1 2 3
1
10 4 1 3 8 5 2 9 10 12 20 17
4
解释:关掉了 4处位置 (2、3、8、10 )上的灯。
对于 100\% 的数据, 1\leq n\leq 10^5 ,保证 dist 在 int 整型范围之内。
int