【提高】平缓的曲线

西西酱在暑假参加了 $N$ 天的集训，每天做出了一道题目，第 $i$ 天做出的题目难度分为 $A_i$。

西西酱很清楚，如果随着时间推移，完成的题目难度分增长过快，就会引起教练的警觉，从而带来不必要的麻烦。

因此，她决定偷偷修改掉某些天完成题目的分数，使得分数序列对于参数 $K$，满足以下要求：

• 对于任意一天的分数 $A_i$，之前不存在任何一天的分数 $A_j$
  • 有 $j \lt i$ 并且 $A_i - A_j \gt (i - j) \times K$

西西酱想知道，至少改掉多少天的分数，就可以达成目标。

需要注意的是，暑假集训的评分系统很奇葩，部分题目的评分可能为负数。

输入格式

第一行两个整数 $N$, $K$，表示训练的天数，以及判定的参数。

第二行 $N$ 个整数 $A_i$，表示每天训练做出题的难度分。

输出格式

输出一行，一个整数，表示最少修改多少天的分数能满足要求。

7 9
10 20 30 40 50 60 70

6

7 10
4262855 5911200 6624873 -1410345 1378369 -6155535 -1297177

4

提示

【样例 1 解释】

• 两两都不满足条件，因此至多保留一个分数，其他都必须改掉，例如改成 10 10 10 10 10 10 10
• 大样例见 rating.zip

【数据范围】

所有测试数据的范围和特点如下表所示：

对于所有测试点，保证 $1 \le N \le 2 \times 10^5$，$0 \le K \le 100$，$-10^7 \le A_i \le 10^7$。

来源

• hfoi 测试2 F：平缓的曲线