配点: 100 点
問題文
K主席负责调节高管所在房间的室温,他要确保高管们尽可能舒适。
现在在房间里 有 N 名高管。每个军官都有 警员编号为 1 从 N ,且不穿夹克。 i (1 \leqq i \leqq N) 的适当温度是 A_i 度。 此外,每位警官都必须穿夹克。 1 每次佩戴,都会找到合适的温度。 T 它下降了。也就是说,官员 i 穿一件夹克 k 佩戴时,军官 i 的适当温度是 A_i-kT 度。
室温 x 度,某次执行的最佳温度 y 度,该官员的不适程度为 它由 |x-y| 表示。然而, 表示 |t| 为 t 的绝对值。每位官员应根据室温采取措施尽量减少不适。 穿适当数量的外套,至少 0 。
这里,主席 K 计算该官员的不适程度的最大值。房间不适程度 我决定将其命名为并设置室温以尽量减少房间的不适程度。但是,您设置的室温必须是整数。
给定有关执行人员和适当温度的信息,编写一个程序来找到房间的最小可能的不适程度。
入力
输入是按以下格式从标准输入给出的。
N T A_1 A_2 \cdots A_N
出力
房间不适级别的最小可能值被输出到标准输出。 1 行上。
制約
- 2 \leqq N \leqq 500\,000.
- 1 \leqq T \leqq 10^9.
- 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- 所有输入值均为整数。
小課題
- (15 点) N = 2.
- (5 点) N \leqq 3\,000,T = 1.
- (30 点) N \leqq 3\,000,T \leqq 2.
- (35 点) N \leqq 3\,000,T \leqq 3\,000.
- (15 点)没有额外的限制。
入力例 1
2 4 19 24
出力例 1
1
例如,如果室温 16 当设置为 1 穿一件夹克 1 穿着这些层可以让您保持适当的温度。 15 学位,军官 1 的不适程度是 |16 - 15| = 1 变为。 官员 2 穿一件夹克 2 穿着这些层可以让您保持适当的温度。 16 学位,军官 2 的不适程度是 |16 - 16| = 0 变为。
此时房间的不适程度为 1 变为。 另外,房间的不适程度 它不能小于 1 ,所以 1 。
此输入示例是一个小作业。 1, 4, 5 满足约束。 如果设置为
入力例 2
3 1 21 19 23
出力例 2
0
例如,如果室温 19 度,房间的不适程度将为 0 变为。因此 0 。
此输入示例是一个小作业。 2, 3, 4, 5 满足约束。 如果设置为
入力例 3
6 8 24 22 21 25 29 17
出力例 3
2
例如,如果室温 15 度,房间的不适程度将为 2 变为。房间的不适程度 2 不能小于 2 。
此输入示例是一个小作业。 4, 5 满足约束。 如果设置为