Problem Description

Chairman K is in charge of adjusting the room temperature for the executives, aiming to ensure they work as comfortably as possible.

There are $N$ executives in the room, each assigned a number from $1$ to $N$. Without wearing a coat, the comfortable temperature for executive $i\ (1 \leq i \leq N)$ is $A_{i}$ degrees. Additionally, each executive's comfortable temperature decreases by $T$ degrees for each coat worn. That is, if executive $i$ wears $k$ coats, their comfortable temperature becomes $A_{i} - kT$ degrees.

If the room temperature is $x$ degrees and an executive's comfortable temperature is $y$ degrees, the discomfort for that executive is $|x - y|$, where $|t|$ denotes the absolute value of $t$. Each executive will wear a sufficient number of coats (at least $0$) to minimize their discomfort based on the room temperature.

Chairman K defines the maximum discomfort among all executives as the room's discomfort level and aims to set the room temperature to minimize this discomfort level. However, the set temperature must be an integer.

Given the information about the executives and their comfortable temperatures, write a program to determine the minimum possible value of the room's discomfort level.

Input Format

The first line contains two integers $N$ and $T$.

The second line contains $N$ integers separated by spaces, $A_1, A_2, \ldots, A_N$.

Output Format

Output a single integer on one line, representing the minimum possible value of the room's discomfort level.

Sample Input and Output

Sample Input #1

2 4
19 24

Sample Output #1

1

Sample Input #2

3 1
21 19 23

Sample Output #2

0

Sample Input #3

6 8
24 22 21 25 29 17

Sample Output #3

2

Notes

For all input data, the following conditions are satisfied:

• $2 \leq N \leq 5 \times 10^5$
• $1 \leq T \leq 10^9$
• $1 \leq A_{i} \leq 10^9\ (1 \leq i \leq N)$

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分