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
def findIndexOfWrong(list, fromNumber):
	for i in range(fromNumber, len(list) - 1):
		if list[i] >= list[i + 1]:
			return i+1
	return -1

line1 = raw_input()
line2 = raw_input()

result = 0

items1 = line1.split(" ")
count = int(items1[0])
add   = int(items1[1])

numbers = line2.split(" ")

for i in range(0, len(numbers)):
	numbers[i] = int(numbers[i])

findIndex = findIndexOfWrong(numbers, 0)

while findIndex != -1:
	addCount = int(-1*(numbers[findIndex] - numbers[findIndex - 1]) / add)
	addCount += 1
	numbers[findIndex] += add*addCount
	result += addCount
	findIndex = findIndexOfWrong(numbers, findIndex - 1)

print result