#61 increasing

Loading problem...

Preparing the statement, recent submissions, and submit form.

#61 increasing | DOJ

Authors: lunarlity

Statement

You are given an integer sequence $A=[A_1,A_2,\ldots,A_N]$ of length $N$ and an integer $K$ .

You can perform the following operation as many times as you want. (Possibly, zero)

Choose an integer $i$ satisfying $1\le i\le N$ , and change $A_i$ to $A_i+K$ . Note that if $K<0$ , this operation is equivalent to subtracting $\vert{}K\vert{}$ from $A_i$ .

Your goal is to make the sequence satisfy the following condition.

$A_1 < A_2 < \cdots < A_N$

Find the minimum number of operations required.

The input is given in the following format.

$N\ K$ $A_1\ A_2\ \cdots \ A_N$

Print the minimum number of operations required to satisfy the given condition.

Sample 1

Input

3 2
4 1 3

Output

Sample 2

Input

3 -2
4 1 3

Output