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 CF11A
{
	public static void main(String[] args)
	{
		Scanner s = new Scanner(System.in);
		String[] meta = s.nextLine().split(" ");
		int count = Integer.parseInt(meta[0]);
		int d = Integer.parseInt(meta[1]);
		String[] seqs = s.nextLine().split(" ");
		int[] seq = new int[count];
		int time = 0;
		seq[0] = Integer.parseInt(seqs[0]);
		for (int i = 1; i < count; i++)
		{
			seq[i] = Integer.parseInt(seqs[i]);
			if (seq[i] <= seq[i - 1])
			{
				time += Math.floor((seq[i - 1] - seq[i]) / d + 1);
				seq[i] += Math.floor((seq[i - 1] - seq[i]) / d + 1) * d;
			}
		}
		System.out.println(time);
		s.close();
	}
}
