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.text.*;
    import java.util.*;
    import java.util.regex.*;

    public class Main{
        static class Run implements Runnable{
            //TODO parameters
            final boolean consoleIO = true;
            final String inFile = "input.txt";
            final String outFile = "output.txt";
            
            int n,d;
            int[] a;
            
            int check(int st) {
                for(int i = st; i < n-1; ++i)
                    if(a[i]>=a[i+1])
                        return i+1;
                
                return n;
            }
            
            @Override
            public void run() {
                n = nextInt();
                d = nextInt();
                a = new int[n];
                
                for(int i = 0; i < n; ++i)
                    a[i] = nextInt();
                
                int bad=1;
                int c = 0;
                while((bad=check(bad-1)) != n) {
                    int dif = a[bad-1]-a[bad];
                    int inc = (int)Math.max(Math.ceil(dif/(double)d),1);
                    
                    a[bad] += inc*d;
                    c+=inc;
                }
                    
                print(c);   
                close();
            }
        //=========================================================================================================================
            BufferedReader in;
            PrintWriter out;
            StringTokenizer strTok;
           
            Run() {
                if (consoleIO) {
                    initConsoleIO();
                }
                else {
                    initFileIO();
                }
            }
           
            void initConsoleIO() {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(new OutputStreamWriter(System.out));
            }
           
            void initFileIO() {
                try {
                    in = new BufferedReader(new FileReader(inFile));
                    out = new PrintWriter(new FileWriter(outFile));
                } catch (FileNotFoundException e) {
                    e.printStackTrace();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
           
            void close() {
                try {
                    in.close();
                    out.close();
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
           
            int nextInt() {
                return Integer.parseInt(nextToken());
            }
           
            double nextDouble() {
                return Double.parseDouble(nextToken());
            }
           
            float nextFloat() {
                return Float.parseFloat(nextToken());
            }
           
            long nextLong() {
                return Long.parseLong(nextToken());
            }
           
            String nextLine() {
                try {
                    return in.readLine();
                } catch (IOException e) {
                    return "__NULL";
                }
            }
           
            boolean hasMoreTokens() {
                return (strTok == null) || (strTok.hasMoreTokens());
            }
           
            String nextToken() {
                while (strTok == null || !strTok.hasMoreTokens()) {
                    String line;
                    try {
                        line = in.readLine();
                        strTok = new StringTokenizer(line);
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
               
                return strTok.nextToken();
            }
           
            void cout(Object o){
                System.out.println(o);
            }
           
            void print(Object o) {
                out.write(o.toString());
            }
            
            void println(Object o) {
                out.write(o.toString() + '\n');
            }
           
            void printf(String format, Object... args) {
                out.printf(format, args);
            }
           
            String sprintf(String format, Object... args) {
            return MessageFormat.format(format, args);
        }
        }
       
        static class Pair<A, B> {
            A a;
            B b;
           
            A f() {
                return a;
            }
           
            B s() {
                return b;
            }
           
            Pair(A a, B b) {
                this.a = a;
                this.b = b;
            }
           
            Pair(Pair<A, B> p) {
                a = p.f();
                b = p.s();
            }
        }
       
        public static void main(String[] args) throws IOException {
            Run run = new Run();
            Thread thread = new Thread(run);
            thread.run();
        }
    }