题目描述

小奶牛设计了一款她认为将成为下一个热门视频游戏的游戏："愤怒的奶牛"。她认为这个游戏的设定是完全原创的：玩家用弹弓将一头奶牛射入一个一维场景中，场景由数轴上不同位置的干草堆组成。

奶牛以足够的力量落地，引爆她着陆点附近的干草堆，这可能会引发连锁反应，导致更多的干草堆爆炸。目标是用一头奶牛引发连锁反应，引爆所有干草堆。

有$N$个干草堆位于数轴上不同的整数位置$x_{1}$,$x_{2}$,$\ldots$,$x_{N}$。如果一头奶牛以威力$R$被发射到位置$x$，这将引发一个"半径为$R$"的爆炸，吞噬$x-R$到$x+R$范围内的所有干草堆。这些干草堆随后会同时爆炸，每个爆炸的半径为$R-1$。任何尚未爆炸的干草堆如果被这些爆炸波及，则会同时爆炸，爆炸半径为$R-2$，依此类推。

请确定发射一头奶牛所需的最小威力$R$，使得如果它落在适当的位置，将引发所有干草堆的爆炸。

输入格式

输入的第一行包含$N$，接下来的$N$行每行包含一个整数$x_{1}$,$x_{2}$,$\ldots$,$x_{N}$。

输出格式

请输出发射奶牛所需的最小威力$R$，以便引爆所有干草堆。答案四舍五入并精确到小数点后一位。

数据范围与提示

• 对于$20\%$的数据，$2 \leq N \leq 100$；
• 对于$50\%$的数据，$2 \leq N \leq 10000$；
• 对于$100\%$的数据，$2 \leq N \leq 50000$，且整数$x_{i} \in [0,10^{9}]$。

样例

5
8
10
3
11
1

3.0

说明

这个例子中，一头奶牛以威力$3$发射到位置$5$，将立即引爆位置$3$和$8$的干草堆。这些干草堆随后同时爆炸，每个爆炸的半径为$2$，吞噬位置$1$和$10$的干草堆，这些干草堆接下来同时爆炸，爆炸半径为$1$，吞噬位置$11$的最后一个干草堆，该干草堆最终以爆炸半径$0$爆炸。