Room Temperature

Interview

Time limit2sMemory limit1024 MB

Summary

Choose an integer room temperature that minimizes the worst officer's distance to their achievable temperatures A_i - kT, with k at least 0.

Level: Medium6 of 10
Topics: Binary search, Sorting, Math
Solved: No attempts yet

Problem

President K is adjusting the room temperature of the officers' room. He wants the officers to be as comfortable as possible.

There are $N$ officers in the room, numbered from 1 to $N$ . When officer $i$ ( $1 \le i \le N$ ) is not wearing a jacket, the appropriate temperature for that officer is $A_i$ degrees. Each jacket the officer wears lowers the appropriate temperature by $T$ degrees. If officer $i$ is wearing $k$ jackets, the appropriate temperature is $A_i - kT$ degrees.

When the room temperature is $x$ degrees and an officer's appropriate temperature is $y$ degrees, that officer's discomfort index is $|x - y|$ , where $|t|$ is the absolute value of $t$ . Each officer wears between 0 and as many jackets as needed to minimize their discomfort index for the given room temperature.

President K defines the room's unpleasantness as the maximum discomfort index among all officers. He sets the room temperature to minimize the room's unpleasantness. The room temperature must be an integer.

Given the officers' information and their appropriate temperatures, write a program that computes the minimum possible room's unpleasantness.

Input

The first line contains $N$ and $T$ . The second line contains $A_1, A_2, \cdots, A_N$ , separated by spaces.

Output

Print one line containing the minimum room's unpleasantness.

Constraints

$2 \le N \le 500\,000$
$1 \le T \le 10^9$
$1 \le A_i \le 10^9$ for all $1 \le i \le N$
All given values are integers.

Examples3

Example 1
Input
```
2 4
19 24
```
Expected output
```
1
```
Example 2
Input
```
3 1
21 19 23
```
Expected output
```
0
```
Example 3
Input
```
6 8
24 22 21 25 29 17
```
Expected output
```
2
```