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
#! /usr/bin/env python3

import itertools
import sys


def main():
    solve()


def solve():
    data = sys.stdin.readlines()
    d, sequence = parse(data)
    output = calc_increase(d, sequence)
    print(output)


def parse(data):
    _, d = tuple(int(s) for s in data[0].split())
    sequence = tuple(int(s) for s in data[1].split())
    return d, sequence


def calc_increase(d, sequence):
    moves = 0
    cur = sequence[0]
    for num in sequence[1:]:
        if num <= cur:
            increases = (cur - num + d) // d
            num += increases * d
            moves += increases
        cur = num
    return moves
    

if __name__ == '__main__':
    main()
