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.*;


public class Main {

    public static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        InputReader.OutputWriter out = new InputReader.OutputWriter(outputStream);

        int n = in.nextInt();
        int d = in.nextInt();
        int [] a = new int[n];
        for (int i = 0; i < a.length; i++) {
            a[i] = in.nextInt();
        }
        int count = 0;
        for (int i = 0; i < a.length - 1; i++) {
            if(a[i+1]<=a[i]) {
                int diff = a[i]-a[i+1];
                int temp = diff/d;
                temp++;
                a[i+1] = a[i+1] + temp*d;
                count+=temp;
            }
        }
        out.println(count);
        out.flush();
    }
    static boolean isPalindrome(char [] c) {
        int i = 0;
        int j = c.length - 1;
        while (i<=j) {
            if(c[i]!=c[j]) return false;
            i++;
            j--;
        }
        return true;
    }
    static boolean isPrime(long n) {
        for (long i = 2; i*i<=n; i++) {
            if(n%i==0) return false;
        }
        return  true;
    }
    static void  reverse(int [] a, int i,int j) {
        while (i<=j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;;
            i++;
            j--;
        }
    }
    static int gcd(int a,int b) {
        return b == 0 ? a : gcd(b,a%b);
    }
}
class Point {
    int index;
    int value;

    public int getIndex() {
        return index;
    }

    public int getValue() {
        return value;
    }
    public Point(int index,int value) {
        this.index = index;
        this.value = value;
    }
}

class InputReader extends BufferedReader {
    StringTokenizer tokenizer;

    public InputReader(InputStream inputStream) {
        super(new InputStreamReader(inputStream), 32768);
    }

    public InputReader(String filename) {
        super(new InputStreamReader(Thread.currentThread().getContextClassLoader().getResourceAsStream(filename)));
    }

    public String next() {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            try {
                tokenizer = new StringTokenizer(readLine());
            } catch (IOException e) {
                throw new RuntimeException();
            }
        }
        return tokenizer.nextToken();
    }

    public Integer nextInt() {
        return Integer.valueOf(next());
    }
    public Long nextLong() {return  Long.valueOf(next());}

    static class OutputWriter extends PrintWriter {
        public OutputWriter(OutputStream outputStream) {
            super(outputStream);
        }

        public OutputWriter(Writer writer) {
            super(writer);
        }

        public OutputWriter(String filename) throws FileNotFoundException {
            super(filename);
        }

        public void close() {
            super.close();
        }
    }
}