709. Friendly Challenges

0

Hard

**Shagundeep** and **Mayank** are two friends who love to challenge each other. In a recent challenge, Mayank provides Shagundeep with an array **A** of **n** numbers and integer **k**. Shagundeep has to find minimum number of moves so that the following condition is satisfied: every element except first should be **k** more than its previous element. In one move Shagundeep can change any element of the array to any integer he wants.

Input Format

The first line contains two space separated integers **n** and **k**.
The second line contains the array in the form of n space-separated integers A[0],A[1],……,A[n-1].

Output Format

Print minimum number of moves.

Example

Input

6 2
1 2 5 7 9 86

Output

2

Constraints

* 2 <= N <= 10^5
* k <= 10^5
* A[i] <= 10^5

Loading...

View Submissions

Console