Make Differences at Least $M$

Time limit1sMemory limit1024 MB

Summary

Given a sequence A and an integer M, find the fewest terms to change so every adjacent difference is at least M, or report -1 if impossible.

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

Problem

Dongwoo is analyzing a sequence $A=\left[ A_1,A_2,\cdots ,A_N \right]$ of length $N$ . In one operation, Dongwoo can change one term $A_i$ of the sequence to any integer he wants. Dongwoo hates doing extra work, so he wants to make every difference between adjacent terms at least $M$ using the fewest possible operations. That is, the goal is $|A_{i+1}-A_i|\geq M$ for all $1\leq i<N$ . Help Dongwoo find the minimum number of operations needed.

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

Print the minimum number of operations needed to make every difference between adjacent terms at least $M$ .

If it is impossible, print -1.

Examples3

Example 1
Input
```
9 3
1 2 2 1 3 3 7 7 1
```
Expected output
```
4
```
Example 2
Input
```
12 2
1 3 2 4 5 6 4 3 3 3 2 3
```
Expected output
```
5
```

Example 3

Input

5 51234652376
1000000000000 985746283947 1000000000000 583726473871 252333425341

Expected output