奶牛 Bessie 设计了一款她认为将成为下一个热门视频游戏的游戏：“愤怒的奶牛”。她认为这个游戏的设定是完全原创的：玩家用弹弓将一头奶牛射入一个一维场景中，场景由数轴上不同位置的干草堆组成；奶牛以足够的力量落地，引爆她着陆点附近的干草堆，这可能会引发连锁反应，导致更多的干草堆爆炸。目标是用一头奶牛引发连锁反应，引爆所有干草堆。
有 N 个干草堆位于数轴上不同的整数位置 x_1, x_2, \ldots, x_N。如果一头奶牛以威力 R 被发射到位置 x，这将引发一个“半径为 R”的爆炸，吞噬 x-R \ldots x+R 范围内的所有干草堆。这些干草堆随后会同时爆炸，每个爆炸的半径为 R-1。任何尚未爆炸的干草堆如果被这些爆炸波及，则会同时爆炸，爆炸半径为 R-2，依此类推。
请确定发射一头奶牛所需的最小威力 R，使得如果它落在适当的位置，将引发所有干草堆的爆炸。
输入的第一行包含 N（2 \leq N \leq 50,000）。接下来的 N 行每行包含一个整数 x_1 \ldots x_N（每个整数都在 0 \ldots 1,000,000,000 范围内）。
请输出发射奶牛所需的最小威力 R，以便引爆所有干草堆。答案应四舍五入并精确到小数点后一位。
5 8 10 3 11 1
3.0
在这个例子中，一头奶牛以威力 3 发射到位置 5，将立即引爆位置 3 和 8 的干草堆。这些干草堆随后同时爆炸，每个爆炸的半径为 2，吞噬位置 1 和 10 的干草堆，这些干草堆接下来同时爆炸，爆炸半径为 1，吞噬位置 11 的最后一个干草堆，该干草堆最终以爆炸半径 0 爆炸。
USACO