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 math
numbers, d=map(int,raw_input().split(' '))
seq=map(int,raw_input().split(' '))
counter=0

for spot in range(numbers-1):
    
    if seq[spot]>=seq[spot+1]:
        x=float(seq[spot]-seq[spot+1])
                
        if x<d:
            seq[spot+1]=seq[spot+1]+d
            counter+=1
        elif x>=d:
            z=x/d
            
            if z%1==0:
                z+=1
                seq[spot+1]=seq[spot+1]+(z*d)
                
                counter+=z
            else:
                z=math.ceil(x/d)
                seq[spot+1]=seq[spot+1]+z*d
                counter+=z
        
        
print int(counter)