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.Scanner;

public class Increse {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt(), d = sc.nextInt(), last = sc.nextInt(), sum = 0;
        while (--n > 0) {
            //System.out.println("last: " + last);
            int b = sc.nextInt();
            if (b <= last) {
               // System.out.println("b: " + b);
                int x = (int) Math.ceil((double) (last - b) / (double) d);
                //System.out.println("x: " + x);
                if(last == b + x * d)
                    x++;
                sum += x;
                b += x * d;
            }
            last = b;
        }
        sc.close();

        System.out.println(sum);
    }
}
