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.io.*;


public class Main {

        static BufferedReader input;
        static PrintWriter output;
        static StreamTokenizer in;
        
        public static void main(String[] args) throws IOException {
        input = new BufferedReader(new InputStreamReader(System.in));
            output = new PrintWriter(System.out);
            int n = nextInt();
            int d = nextInt();
            Integer [] mas = new Integer [n];
            int s = 0;
            for (int i=0; i<n; i++){
                mas[i] = nextInt();
            }
            for (int i=0; i<n-1; i++){
                if (mas[i]>=mas[i+1]){
                    s = s + (mas[i]-mas[i+1])/d + 1;
                    mas[i+1] = mas[i+1] + ((mas[i]-mas[i+1])/d + 1)*d;
                }
            }
            output.write(String.valueOf(s));
            output.flush();
        }

        
    static String nextString() throws IOException {
        if ( in == null ) {
            in = new StreamTokenizer(input);
        }
        in.nextToken();
        return in.sval;
    }


    static double nextDouble() throws NumberFormatException, IOException {
        if ( in == null ) {
            in = new StreamTokenizer(input);
        }
        in.nextToken();
        return in.nval;
    }

    
    static int nextInt() throws NumberFormatException, IOException {
        return (int) nextDouble();
    }
    
    
    static long nextLong() throws NumberFormatException, IOException {
        return (long) nextDouble();
    }
    
 
    static void write(String st) {
                output.write(st);
    }

    
    static void writeln(String st) {
                output.write(st + "\n");
    }
    
}