一条笔直道路用数轴表示。道路上有 n 个必须清理的积雪位置,第 i 个位置的坐标为 x_i。输入顺序可能杂乱,同一坐标也可能重复记录。
清雪车每启动一次,可以选择一个非负整数 s,清理从 s 到 s+L 的整段道路,两端点都包括在内。每次可以自由选择不同的 s,清理区间允许重叠。
只要求所有被记录的积雪位置都至少清理一次,不要求覆盖相邻积雪点之间未被记录的路段。重复坐标被清理一次即可。请计算最少需要启动车辆多少次。
第一行两个整数 n,L,表示积雪记录数和每次清理区间的长度。
第二行 n 个整数 x_1,x_2,\ldots,x_n,表示积雪位置。
对全部数据,1\le n\le100000,1\le L\le10^9,0\le x_i\le10^9。
输出一个整数,表示覆盖所有积雪位置所需的最少启动次数。
7 4 12 1 5 6 2 12 16
3
4 5 5 0 5 0
1
可以清理[1,5]、[6,10]、[12,16],共3次。位置1、6、12两两相距超过4,任意一次都不能覆盖其中两个,因此至少需要3次。坐标12的重复记录不增加需求。
一次清理[0,5]即可覆盖全部记录,两个端点均计入覆盖范围。