小核桃有 $n$ 个数字，他可以使用魔法将数字的大小改变。假设他的法力值是 $x(1 \leq x \leq 10^{9})$，那么对于每个数字而言，他都可以将这个数字增加或者减少 $1 \sim x$，修改数字不消耗法力值。

具体来说，如果一个数字为 2，小核桃的法力值为 3，那么他可以将这个数字减少 $1 \sim 3$，或者增加 $1 \sim 3$，即这个数字可能会变为 $-1,0,1,3,4,5$。当然，小核桃也可以不使用法力，使得这个数字保持不变。

小核桃想要把所有数字变成一样的，害怕法力值太高反噬身体，所以他想知道最低需要多少法力值可以将这些数字变成一样。

输入格式

第一行输入一个正整数 $n$，表示数字的个数，接下来一行输入 $n$ 个正整数，其中第 $i$ 个正整数是 $a_i$

输出格式

输出一行一个正整数表示 $x(1 \leq x \leq 10^{9})$

3
4 1 9

4

说明

法力值为 4 的时候，可以将 4 改成 5，将 1 改成 5，将 9 改成 5，这样所有数字变成一样。

测试点信息

对于所有数据，有 $1 \leq n \leq 10^5, 1 \leq a_i \leq 10^9$