Dao's Race Competition

Interview

Time limit1sMemory limit1024 MB

Summary

Find the fewest tracks to extend by K (each at most once) so the lengths strictly increase, or report -1 if impossible.

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

Problem

Dao is practicing for a race.

Dao prepared $N$ tracks for a race meet. The track raced $i$ -th has length $A_i$ .

The audience wants the race to be exciting, which means the track lengths should keep getting longer. In other words, the race is exciting when $A_1<A_2<\cdots<A_N$ . To do this, Dao can perform the following operation zero or more times.

Choose an index $i$ with $1\le i\le N$ , then increase the length of the $i$ -th track by $K$ . That is, change $A_i$ to $A_i+K$ .
For each $i$ , this operation can be performed at most once.

Determine whether Dao can make the track lengths strictly increasing. If possible, find the minimum number of operations needed.

Input

The first line contains the number of tracks $N$ and the length $K$ by which a track can be extended, separated by a space.

The second line contains the integers $A_1$ , $A_2$ , $\cdots$ , $A_N$ , which give the length of each track, separated by spaces.

Output

If Dao can make the track lengths strictly increasing, print the minimum number of operations needed.

If Dao cannot make the track lengths strictly increasing, print -1.

Constraints

$1\le N\le 10^5$
$1\le K\le 10^9$
$0\le A_i\le 10^9$

Examples3

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