#1516. 苏老师的数字魔法I
-
ID: 1516
Type: Default
1000ms
256MiB
Tried: 4
Accepted: 1
Difficulty: 10
Uploaded By:
sulaoshi
Tags> 苏老师的数字魔法I
说明
苏老师有 $n$ 个数字，他学会了一个很神奇的魔法
对其中一个数字使用魔法时，会使得这个数字发生变化
而变化的幅度则由苏老师的魔法强度 $x$ 来决定
例如对于其中一个数字 $a_i$ 释放魔法，那么苏老师可以将它变成 $[a_i-x, a_i+x]$ 中的任意一个数字
现在作为强迫症的苏老师希望把所有数字变成相同的数字，但是他现在的魔法强度只有 $1$ ，提升魔法强度是很累的！
他想知道他最少需要把魔法强度修炼到多少，才能使得所有数字都变化成同一个数字
P.S. 释放魔法并不会使得魔法强度发生变化，这里认为释放魔法没有消耗
输入格式
第一行输入一个正整数 $n$，表示数字的个数
接下来一行输入 $n$ 个正整数，其中第 $i$ 个正整数是 $a_i$
| 测试点编号 | $n \leq$ | 特殊性质 |
| :---: | :---: | :---: |
| 1-3 | 2 | 无 |
| 4 | $10^5$ | 所有数字均相等 |
| 5-7 | $10^3$ | 无 |
| 8-10 | $10^5$ | 无 |
对于所有数据满足： $1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9$
输出格式
输出一行一个正整数 $x(1 \leq x \leq 10^{9})$ 表示苏老师最少修炼到多少魔法强度
样例
3
4 1 94Statistics
Related
In following contests: