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.Arrays;
import java.math.BigInteger;


public class Main {
   
    
    
    public static void main(String args[]) {
        try {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String temp[]  = br.readLine().split(" ");
            long n = Long.parseLong(temp[0]);
            long d = Long.parseLong(temp[1]);
            String no[] = br.readLine().split(" ");
            int count = 0;
            long last = Long.parseLong(no[0]);
            for(int i = 1; i<no.length;i++){
                long temp1 = Long.parseLong(no[i]);
                if(temp1<=last){
                    long c = (last-temp1);
                    c = (c/d)+1;
                    count += c;
                    temp1 = temp1+(c*d);
                }
                last = temp1;
            }
            System.out.println(count);
            br.close();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
   }