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.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main
{
    public static void main(String args[])
    {
    Scanner in = new Scanner(System.in);
    int n,d;
    n=in.nextInt();
    d=in.nextInt();
    int[] a=new int[n];
    for (int i=0; i<n; ++i)
    {
        a[i]=in.nextInt();
    }
    int res=0;
    int last=a[0];
    for (int i=1; i<a.length; ++i)
    {
        if (a[i]>last)
        {
        last=a[i];
        continue;
        }
        int k=(last-a[i])/d+1;
        res+=k;
        a[i]+=k*d;
        last=a[i];
    }
    System.out.println(res);
    }
}
