AT_agc057_b [AGC057B] 2A + x

给定一个正整数序列 $A = (A_1, A_2, \ldots, A_N)$ 和一个正整数 $X$。你可以对该数列进行任意多次如下操作（也可以一次都不做）： - 选择一个下标 $i$（$1 \leq i \leq N$）以及一个非负整数 $x$，满足 $0 \leq x \leq X$。将 $A_i$ 修改为 $2A_i + x$。 请你求出通过若干次操作后，$\max\{A_1, A_2, \ldots, A_N\} - \min\{A_1, A_2, \ldots, A_N\}$ 可能取得的最小值。

输入从标准输入中给出，格式如下： > $N$ $X$ $A_1$ $A_2$ $\ldots$ $A_N$

输出通过若干次操作后，$\max\{A_1, A_2, \ldots, A_N\} - \min\{A_1, A_2, \ldots, A_N\}$ 可能取得的最小值。

## 限制条件 - $2 \leq N \leq 10^5$ - $1 \leq X \leq 10^9$ - $1 \leq A_i \leq 10^9$ ## 样例解释 1 将 $A_i$ 变为 $2A_i + x$ 的操作记作 $(i, x)$。一种最优的操作序列如下： - $(1, 0)$，$(1, 1)$，$(2, 2)$，$(3, 0)$ 操作后 $A = (21, 18, 24, 20)$，此时 $\max\{A_1, A_2, A_3, A_4\} - \min\{A_1, A_2, A_3, A_4\} = 6$，可以达到。 ## 样例解释 2 一种最优的操作序列如下： - $(1, 5)$，$(1, 5)$，$(2, 5)$，$(2, 1)$，$(3, 2)$，$(3, 3)$，$(4, 0)$，$(4, 3)$ 操作后 $A = (111, 111, 111, 111)$，此时 $\max\{A_1, A_2, A_3, A_4\} - \min\{A_1, A_2, A_3, A_4\} = 0$，可以达到。 ## 样例解释 3 如果一次操作都不做，则 $\max\{A_1, A_2, A_3, A_4\} - \min\{A_1, A_2, A_3, A_4\} = 3$，可以达到。 由 ChatGPT 4.1 翻译