安装监控(Install Cameras)

题目描述

有一条街道上有 n 家商店，位置坐标分别为 x₁, x₂, …, xₙ。社区计划为这条街道安装摄像机，每一台摄像机有一个最大拍摄距离 d，若它被安装在 x 位置，则它可以拍到位于 [x, x+d] 内的所有商店。

请你帮助社区计算出最少需要多少台摄像机才可以覆盖整个街道上的所有商店。

输入格式

第一行：两个正整数 n 与 d； 第二行：n 个正整数 x₁, x₂, …, xₙ

输出格式

单个正整数，表示最少需要的摄像机数量。

数据范围

• 对于 30% 的数据：1 ≤ n ≤ 100
• 对于 60% 的数据：1 ≤ n ≤ 10000
• 对于 100% 的数据：1 ≤ n ≤ 100000，1 ≤ d ≤ 100000，1 ≤ xᵢ ≤ 10⁹
• 给定的数据保证 xᵢ 按顺序给出。

样例输入 #1

6 5
1 4 6 7 9 10

样例输出 #1

2

知识点与难度

本题涉及的知识点从属于 GESP 3级，难度等级：⭐。

测试点分布