402357: GYM100738 C Rating Shuffle

At a prosperious competitive programming website TopForces each user has a personal rating, which is an integer number. There are n users registered, conveniently numbered with numbers from 1 to n. The i-th user has rating of value a_i.

TopForces host regular contests; in a single contest, the rating of each user either increases or decreases by value d. The administrator of the website is curious of the following question: what is the minimal possible number of contests, such that in the end i-th user will have the i-th greatest rating on TopForces?

For clarity, in this problem all users must have distinct ratings after the end of all contests.

The first line of input contains two space-separated integers n and d, the number of users (1 ≤ n ≤ 10⁵) and the change of the rating in a single contest (1 ≤ d ≤ 10⁹). The second line of input contains n space-separated integers a₁, a₂, ..., a_n, the ratings of the users ( - 10⁹ ≤ a_i ≤ 10⁹).

Output a single integer – the minimum possible number of contests such that there exists a scenario in which after all the contests the i-th user has the i-th greatest rating.

3 2
1 3 5

2

2 1
2 2

1

3 5
5 -3 1

1