题目限制

2000 ms 256 M

题目描述

给出一个整数数组 $A$ ，以及一个数字 $K$ ，对于 $A$ 中的每一个元素  $A_i$ ，我们可以选择让 $A_i$ 加上 $k$  或是 减去 $k$ 。然后得到一些数组 $B$ 。我们的目标是让 $B$ 中的最大值和最小值之间的差，尽可能的小。

输出这个最小值。

输入格式

第一行输入一个数 $n$ ，表示 $A$ 中元素个数； 第二行输入 $n$ 个数，表示 $A$ 中元素，以空格隔开； 第三行输入一个数 $K$ ； 其中 $1\le n\le 10000$ ， $0\le A[i]\le 10000$ ， $0\le K\le 10000$ .

输出格式

输出一个数表示最小差值

数据范围

对于 $15\%$ 的数据， $1 \le n \le 5$ ；

对于 $50\%$ 的数据， $1 \le n \le 1000$ ；

对于 $100\%$ 的数据， $1 \le n \le 10000, 0 \le A[i] \le 10000, 0 \le K \le 10000$ ；

输入样例 1

3
1 3 6
3

输出样例 1

3

样例解释

将 $1,3,6$ 更新为 $4,6,3$ 可得最大最小值之差为 $3$ ，没有其他更优的解