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

public class Main {
//	static Scanner in;
	static PrintWriter out;
	static StreamTokenizer in; static int next() throws Exception {in.nextToken(); return (int) in.nval;}

	public static void main(String[] args) throws Exception {
//		in = new Scanner(System.in);
		out = new PrintWriter(System.out);
		in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

		int n = next();
		int d = next();
		int[] x = new int[n];
		for (int i = 0; i < n; i++) x[i] = next();

		int answ = 0;
		for (int i = 1; i < n; i++) {
			int k = x[i] - x[i - 1];
			if (k > 0) continue;
			k = -k;
			k++;
			int t = (k + d - 1)/d;
			answ += t;
			x[i] += t*d;
		}

		out.println(answ);

		out.close();
	}
}