题目描述

题目译自 JOI 2024 Final T1 「室温 / Room Temperature」

K 董事长负责调节高管们的房间的室温，他希望高管们能尽可能舒适地工作。

现在房间里有 $N$ 位高管。每位高管都有一个从 $1$ 到 $N$ 的编号。不穿外套时，高管 $i$（$1 \leq i \leq N$）的舒适温度是 $A_{i}$ 度。另外，每位高管每穿一件外套，舒适温度就会降低 $T$ 度。也就是说，高管 $i$ 如果穿了 $k$ 件外套（$k \geq 0$），那么高管 $i$ 的舒适温度就是 $A_{i} - kT$ 度。

如果房间的温度是 $x$ 度（$x$ 为整数），某位高管的舒适温度是 $y$ 度，那么这位高管的不舒适度就是 $|x - y|$。每位高管会根据房间的温度，穿上大于等于 $0$ 件合适的外套，使得不舒适度最小。

K 董事长把高管们的不舒适度的最大值称为房间的不舒适度，并决定要把房间的温度设定为使得房间的不舒适度最小的值。设定的温度必须是整数。

给定高管和舒适温度的信息，编写程序求出房间的不舒适度可能的最小值。

输入格式

第一行包含两个整数 $N$ 和 $T$。

第二行包含用空格分隔的 $N$ 个整数 $A_1, A_2, \ldots, A_N$。

输出格式

输出一行一个整数，表示房间的不舒适度可能的最小值。

样例 1

输入

2 4
19 24

输出

1

样例说明

如果把房间的温度设定为 $16$ 度：

• 高管 $1$ 穿 $1$ 件外套，舒适温度变为 $19 - 1 \times 4 = 15$ 度，不舒适度为 $|16 - 15| = 1$。
• 高管 $2$ 穿 $2$ 件外套，舒适温度变为 $24 - 2 \times 4 = 16$ 度，不舒适度为 $|16 - 16| = 0$。

房间的不舒适度为 $1$，且无法降低到 $1$ 以下，故输出 $1$。

该样例满足子任务 $1,4,5$ 的限制。

样例 2

输入

3 1
21 19 23

输出

0

样例说明

如果把房间的温度设定为 $19$ 度：

• 高管 $1$ 穿 $2$ 件外套，舒适温度变为 $21 - 2 \times 1 = 19$ 度，不舒适度为 $0$。
• 高管 $2$ 不穿外套，舒适温度为 $19$ 度，不舒适度为 $0$。
• 高管 $3$ 穿 $4$ 件外套，舒适温度变为 $23 - 4 \times 1 = 19$ 度，不舒适度为 $0$。

房间的不舒适度为 $0$，故输出 $0$。

该样例满足子任务 $2,3,4,5$ 的限制。

样例 3

输入

6 8
24 22 21 25 29 17

输出

2

样例说明

如果把房间的温度设定为 $15$ 度，房间的不舒适度为 $2$，且无法降低到 $2$ 以下，故输出 $2$。

该样例满足子任务 $4,5$ 的限制。

数据范围与提示

对于所有输入数据，满足：

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

详细子任务附加限制及分值如下表所示：

子任务	附加限制	分值
$1$	$N=2$	$15$
$2$	$N \leq 3000$，$T=1$	$5$
$3$	$N \leq 3000$，$T \leq 2$	$30$
$4$	$N \leq 3000$，$T \leq 3000$	$35$
$5$	无附加限制	$15$