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
w=raw_input().split()
n=int(w[0])
e=int(w[1])
d=[]
c=[]
m=raw_input().split()

for x in m:
    d.append(int(x))
    c.append(int(x))
c.sort(cmp=None, key=None, reverse=False)
count =0;
for i in range(len(c)):
    if i>0:
        if c[i]==d[i]:
            ma=d[i-1]
        else:
            ma=max([c[i],d[i-1]])
    else: 
        if c[i]==d[i]:
            continue
        else:
            ma=c[i]
    if d[i]<=ma:
        addi=((ma-d[i])/e)+1
        d[i]+=(e*addi)
        count+=addi
     
print count