A sequence a0, a1, ..., at - 1 is called increasing if ai - 1 < ai for each i: 0 < i < t.

You are given a sequence b0, b1, ..., bn - 1 and a positive integer d. In each move you may choose one element of the given sequence and add d to it. What is the least number of moves required to make the given sequence increasing?

Input

The first line of the input contains two integer numbers n and d (2 ≤ n ≤ 2000, 1 ≤ d ≤ 106). The second line contains space separated sequence b0, b1, ..., bn - 1 (1 ≤ bi ≤ 106).

Output

Output the minimal number of moves needed to make the sequence increasing.

Examples

Input

4 2
1 3 3 2


Output

3
import java.util.*;
import java.io.*;
public class MyClass {
    public static void main(String args[]) {
        Scanner sc=new Scanner(System.in);
        PrintWriter out=new PrintWriter(System.out);
          int n =sc.nextInt();
        int d =sc.nextInt();
        long last = sc.nextInt();
        long res = 0;
        for (int i = 0; i < n - 1; ++i) {
            long cur =sc.nextInt();
            if (cur <= last) {
                long by = (last + d - cur) / d;
                res += by;
                last = cur + by * d;
            } else {
                last = cur;
            }
        }
     out.println(res);
     sc.close();
     out.close();
 }
}