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 cls_11_IncreasingSequence {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        
        int n = scan.nextInt();
        int d = scan.nextInt();
        
        int[] s = new int[n];
        
        for (int i = 0; i < n; i++) {
            s[i] = scan.nextInt();
        }
        
        scan.close();
        
        int startIndex = 0;
        
        for (int i = 1; i < n; i++) {
            if(s[i-1] >= s[i])
            {
                startIndex = i;
                break;
            }
        }
        
        int moves = 0;
        
        if(startIndex == 0)
            System.out.println(moves);
        else
        {
            for (int i = startIndex; i < n; i++) {
                int dif = s[i - 1] - s[i];

                if(dif == 0)
                {
                    moves ++;
                    s[i] += d;
                }
                else
                {

                    double t = Float.parseFloat(Integer.toString(dif+1));
                    double y = Float.parseFloat(Integer.toString(d));

                    double f = t / y;

                    int AddOne = 0;

                    if(((dif+1) / d) < f)
                        AddOne = 1;



                    moves += ((dif + 1) / d) + AddOne;
                    s[i] += (((dif + 1) / d) + AddOne) * d;
                }
                
                for (int u = 1; u < n; u++) {
                    if(s[u-1] >= s[u])
                    {
                        startIndex = u;
                        i = startIndex - 1;
                        break;
                    }
                }
            }

            System.out.println(moves);
        }
    }
}
