题目描述

在《愤怒的奶牛》这款游戏中，你的任务是精准地发射一头奶牛，利用它引发的连锁反应来引爆地图上所有的干草捆。

游戏规则如下：

1. 场景: 在一条一维数轴上，有 $N$ 个干草捆，它们各自位于不同的整数坐标 $x_1, x_2, \ldots, x_N$。

2. 发射: 你可以选择一个发射功率 $R$ 和一个着陆点 $x$（注意：$x$ 可以是小数）。

3. 初始爆炸: 奶牛以功率 $R$ 降落在 $x$ 点，这将立即引爆一个半径为 $R$ 的区域。所有位于闭区间 $[x-R, x+R]$ 内的干草捆都会被引爆。

4. 连锁反应: 这是一个分阶段、同步进行的过程。

   • 第 1 轮: 在初始爆炸中被引爆的所有干草捆，会同时发生爆炸，但爆炸半径减小为 $R-1$。
   • 第 2 轮: 在第 1 轮爆炸中首次被波及（新引爆）的干草捆，会同时发生爆炸，爆炸半径进一步减小为 $R-2$。
   • 后续: 这个过程持续进行，每一轮新引爆的干草捆都会以再减 1 的半径爆炸。当没有新的干草捆被引爆，或者爆炸半径小于 0 时，连锁反应结束。

你的任务是： 找出能够引爆所有 $N$ 个干草捆所需的最小发射功率 $R$。

输入格式

• 第一行包含一个整数 $N$（$2 \le N \le 50,000$），代表干草捆的数量。
• 接下来 $N$ 行，每行包含一个整数 $x_i$（$0 \le x_i \le 1,000,000,000$），代表一个干草捆的位置。

输出格式

• 输出一个浮点数，代表所需的最小功率 $R$。
• 答案请四舍五入到小数点后一位。

样例

输入样例

5
8
10
3
11
1

输出样例

3.0

样例说明

在本例中，干草捆的位置排序后为：1, 3, 8, 10, 11。 当最小发射功率 $R=3.0$ 时，我们可以选择将奶牛降落在 $x=5.5$ 的位置。

• 初始爆炸 (半径 $R=3$):

  • 奶牛降落在 $5.5$。爆炸范围为 $[5.5-3, 5.5+3] = [2.5, 8.5]$。
  • 这会引爆位置在 3 和 8 的干草捆。

• 第 1 轮连锁反应 (半径 $R-1=2$):

  • 位置 3 的干草捆爆炸，范围为 $[3-2, 3+2] = [1, 5]$，引爆了位置 1 的干草捆。
  • 位置 8 的干草捆爆炸，范围为 $[8-2, 8+2] = [6, 10]$，引爆了位置 10 的干草捆。

• 第 2 轮连锁反应 (半径 $R-2=1$):

  • 位置 1 的干草捆爆炸，范围为 $[1-1, 1+1] = [0, 2]$，没有引爆新的干草捆。
  • 位置 10 的干草捆爆炸，范围为 $[10-1, 10+1] = [9, 11]$，引爆了位置 11 的干草捆。

• 第 3 轮连锁反应 (半径 $R-3=0$):

  • 位置 11 的干草捆爆炸，范围为 $[11-0, 11+0] = [11, 11]$，没有引爆新的干草捆。

至此，所有干草捆（1, 3, 8, 10, 11）均被引爆。可以证明，不存在比 $3.0$ 更小的 $R$ 能完成目标。