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 implements Runnable {

	PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
	Scanner in = new Scanner(new InputStreamReader(System.in));
	
	private void solution() throws IOException {
		int n = in.nextInt();
		int d = in.nextInt();
		long prev = 0;
		int res = 0;
		for (int i = 0; i < n; ++i) {
			long cur = Long.parseLong(in.next());
			if (cur <= prev) {
				long add = (long) (Math.ceil((double) (prev - cur + 1) / d));
				res += add;
				prev = cur + add * d;
			} else {
				prev = cur;
			}
		}
		out.println(res);
	}

	@Override
	public void run() {
		try {
			solution();
			in.reader.close();
			out.close();
		} catch (Throwable e) {
			e.printStackTrace();
			System.exit(1);
		}
	}
	
	private class Scanner {

		private StringTokenizer tokenizer;
		private BufferedReader reader;

		public Scanner(Reader in) {
			reader = new BufferedReader(in);
			tokenizer = new StringTokenizer("");
		}

		public boolean hasNext() throws IOException {
			while (!tokenizer.hasMoreTokens()) {
				String tmp = reader.readLine();
				if (tmp == null)
					return false;
				tokenizer = new StringTokenizer(tmp);
			}
			return true;
		}

		public String next() throws IOException {
			hasNext();
			return tokenizer.nextToken();
		}

		public String nextLine() throws IOException {
			tokenizer = new StringTokenizer("");
			return reader.readLine();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
	}

	public static void main(String[] args) throws IOException {
		new Thread(null, new Main(), "Main", 1 << 28).start();
	}
}
