402357: GYM100738 C Rating Shuffle
Description
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 ai.
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.
InputThe first line of input contains two space-separated integers n and d, the number of users (1 ≤ n ≤ 105) and the change of the rating in a single contest (1 ≤ d ≤ 109). The second line of input contains n space-separated integers a1, a2, ..., an, the ratings of the users ( - 109 ≤ ai ≤ 109).
OutputOutput 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.
ExamplesInput3 2Output
1 3 5
2Input
2 1Output
2 2
1Input
3 5Output
5 -3 1
1