Minimizing Maximum Discomfort in the Executive Rooms

Chairman K needs to set the room temperature at an integer value (x) in order to make the high‐level executives as comfortable as possible. There are (N) executives, numbered from (1) to (N). When an executive (i\ (1 \le i \le N)) does not wear any coat, his comfortable temperature is (A_i) degrees. For every coat he wears, his comfortable temperature decreases by (T) degrees. In other words, if executive (i) wears (k) coats, his comfortable temperature becomes (A_i - kT) degrees.

If the room temperature is (x) and an executive’s comfortable temperature is (y), his discomfort is defined as (|x - y|) (where (|t|) denotes the absolute value of (t)). Each executive will choose a nonnegative integer number of coats so that his own discomfort is minimized. The room’s discomfort is defined as the maximum discomfort among all executives.

The task is to choose an integer room temperature (x) so that the room discomfort is as small as possible, and then output this minimum possible room discomfort.

It can be shown that an optimal strategy is to set (x) no larger than the smallest (A_i). In that case, every executive is allowed to choose a number of coats yielding a comfortable temperature in the arithmetic sequence [ A_i,;A_i-T,;A_i-2T,;\dots ] which (when (x \le A_i)) gives a discomfort which depends only on the difference in their values modulo (T). More precisely, if we define (r_i = A_i \bmod T) (with (0 \le r_i < T)) and choose (x = r + kT) with (r) chosen in ([0, T-1]) and an appropriate integer (k) so that (x \le \min_i;A_i), then each executive (i) will achieve a discomfort [ \min\Bigl(|r_i - r|,;T-|r_i - r|\Bigr). ] Thus the problem reduces to the following: Given (N) points (r_1, r_2, \dots, r_N) on a circle of circumference (T), choose an integer (r) ((0 \le r < T)) so that (\max_{1\le i\le N} \min\bigl(|r_i - r|, T-|r_i-r|\bigr)) is minimized.

Your program should read (N) and (T) and then the (N) integers (A_1, A_2, \dots, A_N) and output the minimal achievable room discomfort.

inputFormat

The first line contains two integers \(N\) and \(T\) (number of executives and the temperature penalty per coat).

The second line contains \(N\) integers \(A_1, A_2, \dots, A_N\), where \(A_i\) is the comfortable temperature (in degrees) for executive \(i\) when not wearing any coat.

outputFormat

Output a single integer, which is the minimal possible room discomfort.

sample

3 10
1 3 8

3