题目描述

奶牛贝西（$\red{Bessie the cow}$）设计了一款她认为将成为下一款热门视频游戏的游戏："愤怒的奶牛"。

她认为这是完全原创的前提，即玩家用弹弓将奶牛射入一维场景，该场景由位于数字线上不同点的一组干草捆组成；奶牛以足够的力量着陆，在其着陆点附近引爆干草捆，这反过来可能会引发连锁反应，导致更多干草捆爆炸。

目标是用一头奶牛引发连锁反应，引爆所有干草捆。有$\red{N}$个干草捆位于数字行上不同的整数位置$\red{x1，}$$\red{x2，…，}$$\red{xN}$。如果奶牛在动力$\red{R}$着陆位置$\red{x}$时下水，这将导致"半径$\red{R}$"爆炸，吞没$\red{x}$范围内的所有干草捆$\red{R，... ， }$$\red{x+Rx}$。

然后这些干草捆本身爆炸（全部同时发生），每个爆炸半径为$\red{R−1.}$在这些爆炸中捕获的任何尚未爆炸的捆都会以爆炸半径$\red{R}$（同时）爆炸$\red{−2R−2，}$依此类推。

请确定单头奶牛可以发射的最小功率$\red{R，}$以便如果奶牛降落在适当的位置，它将导致随后引爆场景中的每个干草捆。

输入格式

第一行输入包含$\red{N（}$$\red{2≤}$$\red{N≤}$$\red{50,000). }$其余的$\red{N}$行都包含整数$\red{x1…}$$\red{xN}$每个在$\red{(0}$$\red{...100000000）}$。

输出格式

请输出启动奶牛以引爆所有干草捆所需的最小功率$\red{R}$。

答案应四舍五入并精确打印到小数点后$\red{1}$位

样例

输入样例

5
8
10
3
11
1

输出样例

3.0

提示

在本例中，在位置$\red{5}$以动力$\red{3}$发射的奶牛将立即引爆位置$\red{3}$和$\red{8}$处的干草捆。

然后，它们以爆炸半径$\red{2}$（同时）爆炸，吞没位置$\red{1}$和$\red{10}$处的捆，然后以爆炸半径$\red{1}$（同时）爆炸，吞没位置$\red{11}$处的最终 捆，最后以爆炸半径$\red{0}$爆炸。