曹文信息在线OJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

5425: Increasing Sequence

Memory Limit：256 MB Time Limit：2.000 S
Judge Style：Text Compare Creator：
Submit：0 Solved：0
SubmitSubmit RecordStatisticsWeb BoardShowOff!

Description

time limit per test
1 second
memory limit per test
64 megabytes
input
standard input
output
standard output

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