Problem Description

Chairman K is responsible for adjusting the room temperature for the executives. He wants them to work as comfortably as possible.

There are $N$ executives in the room. Each executive is assigned an ID from $1$ to $N$. Without wearing a coat, executive $i\ (1 \leq i \leq N)$ has a comfortable temperature of $A_i$ degrees. Also, for each coat an executive wears, their comfortable temperature decreases by $T$ degrees. That is, if executive $i$ wears $k$ coats, then executive $i$'s comfortable temperature becomes $A_i - kT$ degrees.

If the room temperature is $x$ degrees and an executive's comfortable temperature is $y$ degrees, then this executive's discomfort is $|x - y|$, where $|t|$ denotes the absolute value of $t$. Each executive will, depending on the room temperature, wear an appropriate number of coats $k \geq 0$ to minimize their discomfort.

Chairman K defines the maximum discomfort among all executives as the room's discomfort, and he decides to set the room temperature to a value that minimizes the room's discomfort. However, the chosen temperature must be an integer.

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

Input Format

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

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

Output Format

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

2 4
19 24

1

3 1
21 19 23

0

6 8
24 22 21 25 29 17

2

Hint

For all input data, the following constraints hold:

• $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)$

The detailed additional constraints and scores for each subtask are shown in the table below.

Translated by ChatGPT 5