Keep Differences at Most M

Time limit3sMemory limit1024 MB

Summary

Find the fewest elements to change so every adjacent pair differs by at most M, where each changed value can be any integer.

Level: Medium7 of 10
Topics: Dynamic programming, Math, Array
Solved: No attempts yet

Problem

Dongwoo is analyzing a sequence $A=[A_1, A_2, \cdots, A_N]$ of length $N$ . In one operation, Dongwoo can change one element $A_i$ of the sequence to any integer he wants. Dongwoo does not like tedious work, so he wants every pair of adjacent elements to differ by at most $M$ using as few operations as possible. In other words, the goal is $|A_{i+1}-A_i| \leq M$ for all $1 \leq i < N$ . Help Dongwoo find the minimum number of operations required.

Input

The first line contains two integers $N$ ( $1 \leq N \leq 10^6$ ) and $M$ ( $1 \leq M \leq 10^{12}$ ), separated by a space. The second line contains $N$ integers $A_1, A_2, \cdots, A_N$ ( $1 \leq A_i \leq 10^{12}$ ), separated by spaces.

Output

On the first line, print the minimum number of operations needed to make every pair of adjacent elements differ by at most $M$ .

If it is impossible, print -1.

Examples2

Example 1
Input
```
9 3
1 2 2 1 3 3 7 7 1
```
Expected output
```
2
```
Example 2
Input
```
10 5
2 8 7 5 15 18 17 20 5 16
```
Expected output
```
3
```