C. Rating Shuffle
time limit per test
0.3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.

Input

The 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).

Output

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.

Examples
Input
3 2
1 3 5
Output
2
Input
2 1
2 2
Output
1
Input
3 5
5 -3 1
Output
1