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

/**
 *
 * @author Haya
 */
public class JavaApplication141 {

    public static void main(String[] args) {
        
        FastReader in = new FastReader();
        
        int n = in.nextInt();
        int dif = in.nextInt();
        
        int nums[] = new int[n];
        
        for (int i = 0; i < n; i++) {
            nums[i]=in.nextInt();
        }
        

        
        int count = 0;
        
        for (int i = 1; i < n; i++) {
            
            if (nums[i-1]<nums[i])
                continue;
            
            int toadd = (int) Math.ceil((nums[i-1]-nums[i]+1)/(dif*1.0));
         
            count += toadd;
            nums[i]+=toadd*dif;
        }
        
        System.out.println(count);
        
        
    }

    public static class FastReader {

        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String string = "";
            try {
                string = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return string;
        }

    }

}
