#wch222. 炸怪物

炸怪物

【题目描述】

从左到右有 nn 只怪物,位置依次为 a1,…,ana_1,\ldots,a_n。一颗炸弹可以炸掉某个长度不超过 DD 的闭区间内的所有怪物。

炸弹可以放在任意位置,求最多能炸掉多少只怪物。

【输入格式】

nn   DD

a1a_1   ⋯\cdots   ana_n

【输出格式】

输出最多能炸掉的怪物数。

【样例】

6 4
1 2 4 7 8 9
3

【数据范围】

  • 1≤n≤1000001\le n\le100000
  • 0≤D≤1090\le D\le10^9
  • 0≤a1≤a2≤⋯≤an≤1090\le a_1\le a_2\le\cdots\le a_n\le10^9