题目描述

给定一个正整数序列 $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\}$ 可能取得的最小值。

样例 1

输入

4 2
5 8 12 20

输出

6

样例 2

输入

4 5
24 25 26 27

输出

0

样例 3

输入

4 1
24 25 26 27

输出

3

样例 4

输入

10 5
39 23 3 7 16 19 40 16 33 6

输出

13

说明/提示

限制条件

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