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
n,d = map(int,input().split())
seq = list(map(int,input().split()))
ans = 0
# def recur(seq,d,i):
#     if seq[i + 1] > seq[i]:
#         return 0
#     else:
#         seq[i + 1] += d
#         return recur(seq,d,i) + 1
# for i in range(len(seq)-1):
#     ans += recur(seq,d,i)
# print(ans)

for i in range(len(seq)-1):
    if seq[i+1] - seq[i] <= 0:
        ans += (seq[i]-seq[i+1]) // d + 1
        seq[i+1] += d * ((seq[i]-seq[i+1]) // d + 1 )
print(ans)