Increasing Sequence

1000ms

65536K

Description:

A sequence a₀, a₁, ..., a_t - 1 is called increasing if a_i - 1 < a_i for each i: 0 < i < t.

You are given a sequence b₀, b₁, ..., b_n - 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 ≤ 10⁶). The second line contains space separated sequence b₀, b₁, ..., b_n - 1 (1 ≤ b_i ≤ 10⁶).

Output:

Output the minimal number of moves needed to make the sequence increasing.

Sample Input:

4 2
1 3 3 2

Sample Output:

Informação

Provedor Codeforces

Código CF11A