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.util.*;
import java.lang.Math;
import java.io.*;

public class Solution
{
    public static void main(String[] args) throws IOException
    {
        FastReader in=new FastReader(System.in);
        int n=in.nextInt();
        int k=in.nextInt();
        Long[] arr=new Long[n];
        for(int i=0;i<n;i++)
            arr[i]=in.nextLong();
        long ans=0;
        for(int i=1;i<n;i++)
        {
            if(arr[i]-arr[i-1]<=0)
            {
                long factor=(arr[i-1]-arr[i])/k+1;
                arr[i]+=factor*k;
                ans+=factor;
            }
        }
        System.out.println(ans);
    }
}

class Graph
{
    private int V;
    private ArrayList<Integer> adj[];
    private static Set<Integer> visited;
    
    public Graph(int v)
    {
        V=v+1;
        adj=new ArrayList[V];
        visited=new HashSet<>();
        for(int i=1;i<=v;i++)
            adj[i]=new ArrayList<>();
    }
    
    public void addEdge(int a,int b)
    {
        adj[a].add(b);
        adj[b].add(a);
    }
    
    public int dfs(int a)
    {
        int r=1;
        if(visited.contains(a))
            return 0;
        else if(adj[a].size()!=2)
            return 0;
        visited.add(a);
        for(int i=0;i<adj[a].size();i++)
        {
            if(!visited.contains(adj[a].get(i)))
                r=dfs(adj[a].get(i));
        }
        return r;
    }
}

class FastReader
{
    static BufferedReader br;
    static StringTokenizer st;
    
    public FastReader(InputStream in) throws IOException
    {
        br=new BufferedReader(new InputStreamReader(in));
    }
    
    static String next() throws IOException
    {
        if(st==null || !st.hasMoreElements())
        {
            st=new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }
    
    static int nextInt() throws IOException
    {
        return Integer.parseInt(next());
    }
    
    static long nextLong() throws IOException
    {
        return Long.parseLong(next());
    }
    
    static String nextLine() throws IOException
    {
        return br.readLine();
    }
    
    static double nextDouble() throws IOException
    {
        return Double.parseDouble(next());
    }
}