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 翻译