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.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;




public class CodeForces{
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));   
    static StringTokenizer token;
    public static void main(String args[])throws Exception{                
        token = new StringTokenizer(reader.readLine());
        int n = Integer.parseInt(token.nextToken());
        int d = Integer.parseInt(token.nextToken());
        token = new StringTokenizer(reader.readLine());
        int [] list= new int[n];
        for (int i = 0; i < n; i++) {
            list[i] = Integer.parseInt(token.nextToken());
        }
        int counter= 0;
        for (int i = 0; i < n - 1; i++) {
            if(list[i + 1] <= list[i]){
                int temp = list[i] - list[i + 1];
                //sama
                if(temp == 0){
                    counter++;
                    list[i + 1] += d;                
                }else{
                    int lol = temp;
                    temp = (int) Math.ceil(1.0 * temp/d);
                    if(lol%d==0){
                        temp++;
                    }                                   
                    counter += temp;
                    list[i + 1] += (temp*d);
                }                                    
            }             
        }
        
        if(list[n - 1] <= list[n - 2]){            
            int temp = list[n - 2] - list[n - 1];
            //sama
            if(temp == 0){
                counter++;                
            }else{               
                int lol = temp;
                temp = (int) Math.ceil(1.0 * temp/d);
                if(lol%d==0){
                    temp++;
                }                                   
                counter += temp;                    
            }                                                
        }
        System.out.println(counter);
    }
}