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;
import java.io.PrintWriter;
import java.util.stream.*;


public class Increasing11A implements Runnable {
    private Scanner in = new Scanner(System.in);
    private PrintWriter out = new PrintWriter(System.out);

    int ans;
    int n;
    int d;
    int[] b;

    public static void main(String[] args) {
	new Thread(new Increasing11A()).start();
    }

    private void read() {
	n = in.nextInt();
	d = in.nextInt();
	b = new int[n];
	for(int i = 0 ; i<n; i++){
	    b[i] = in.nextInt();
	}
    }

    private void solve() {
	ans = 0;
	for(int i = 1; i<n; i++){
	    if(b[i] <= b[i-1]){
		int diff = b[i-1]+1-b[i]; //difference between where we are and what we need
		if( diff % d == 0){
		    ans += diff/d;
		    b[i] += diff;
		}
		else{
		    ans += diff/d+1;
		    b[i]+= (diff/d+1)*d;
		}
	    }
	}
	//System.out.println(ans);
    }

    private void write() {
	out.println(ans);
    }
    public void run() {
	read();
	solve();
	write();
	out.close();
    }
}

