问题描述

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

输入

输入共2行。 第一行2个整数n和d，n表示数列中数的数量，d含义如题目所示， 第二行n个整数bi，表示原始数列。 （2≤n≤2000,1≤d≤$10^6$,1≤bi≤$10^6$）

输出

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

Samples

4 2
1 3 3 2

3

Limitation

1s, 1024KiB for each test case.