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.math.BigInteger;
import java.util.Arrays;
import java.util.Iterator;
import java.util.Scanner;
import java.util.TreeSet;
public class Main{

	static int count = 0;
	static int [] arr ;
	public static void main(String[] args) {
      
		Scanner in = new Scanner(System.in);

		int n = in.nextInt();
		int d = in.nextInt();
	    arr = new int [n];
		
		for(int i=0 ; i<n ; i++){
			arr[i] = in.nextInt();
			
			if(i != 0){
				
				count(arr[i-1] , arr[i] , d , i);
			}
		  } //end for
	
		System.out.println(count);
	}
	
	//count method
	public static int count(int a , int b , int d , int index) {
		
		
		if(b <= a) {
			
			int dif = a - b ;
			
			if(dif < d){
			   count++;
			   arr[index] += d;
			} //end if
			
			else {
					count += dif / d + 1 ;
					arr[index] += (dif / d + 1) * d;
			} //end else
		} //end if
		
		return count;
	}
}