Block Play

Interview

Time limit2sMemory limit512 MB

Summary

Each tower can be changed to any height at least 1 in one minute. Find the fewest towers to change so that consecutive heights differ by K.

Level: Medium4 of 10
Topics: Math, Implementation, Brute force, Array
Solved: No attempts yet

Problem

Wookje has a very large supply of blocks of height 1 and built N towers by stacking them. The towers stand in a row, and the height of the i-th tower from the left is Ai.

Wookje's favorite integer is K. So he wants the height difference between each pair of adjacent towers to be K, that is, Ai+1 - Ai = K must hold.

In one minute, Wookje can pick one tower and either place more blocks on it to make it taller or remove blocks from it to make it shorter. Find the time needed to make the height difference between every pair of adjacent towers equal to K. Wookje's hands are very fast, so the number of blocks he can place or remove in one minute is infinite.

A tower's height must always be at least 1.

Input

The first line gives the number of towers N and Wookje's favorite integer K.

The second line gives the tower heights A1, A2, ..., AN.

Output

On the first line, print the minimum time needed to make the height difference between every pair of adjacent towers equal to K.

Constraints

1 ≤ N, K ≤ 1,000
1 ≤ Ai ≤ 1,000

Examples2

Example 1
Input
```
4 1
1 2 1 5
```
Expected output
```
2
```
Example 2
Input
```
4 1
1 2 3 4
```
Expected output
```
0
```