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.*;
public class Increasing_Sequence {
  public static void main(String[]args){
    int n;
    Scanner input = new Scanner(System.in);
    n = input.nextInt();
    double d = input.nextDouble();
    double[] arr = new double[n];
    int move = 0;
    for(int i = 0;i < n;i++){
      arr[i] = input.nextDouble();
      if(i == 0)
       continue;
      else{
        if(arr[i-1] >= arr[i]){
          int p = 0;
          if(((int)((arr[i-1])-arr[i])%(int)d) == 0){
           p = (int)Math.ceil((arr[i-1]-arr[i])/d) + 1;
          }
          else{
            p = (int)Math.ceil((arr[i-1]-arr[i])/d);
          }
          
          if(p == 0){
            p = 1;
          }
          arr[i] = arr[i] + (d * p);
          move = move + p;
        }
      }
    }
    /* for(double i : arr){
      System.out.print(i + " ");
    } */
    System.out.print(move);
  }
}