递增数列

题目描述

在童话王国"递增乐园"，居民们崇尚递增数列的和谐美。但王国里有些数列并不递增，这让国王很头疼。于是，国王提出挑战：谁能用最少的操作次数把非递增数列变成递增数列，就能获得大奖。但是每次操作只能给数列中的一个数加上一个整数 $d$。

输入格式

输入共 $2$ 行。

第一行 $2$ 个整数 $n$ 和 $d$，$n$ 表示数列中数的数量，$d$ 含义如题目所示。

第二行 $n$ 个整数，表示原始数列。

输出格式

一行一个整数 $m$，表示最少 $m$ 次操作能把这个数列变为递增数列。

样例输入 #1

4 2
1 3 3 2

样例输出 #1

3

数据范围

$2\le n\le 2000$，$1\le d\le 10^6$，$1\le b_i\le 10^6$。

知识点与难度

本题涉及的知识点从属于 GESP 5级（贪心、一维数组），难度等级：Mid-（⭐⭐⭐⭐）。

测试点分布