P3132 [USACO16JAN] Angry Cows G

题目描述

奶牛 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$，以便引爆所有干草堆。答案应四舍五入并精确到小数点后一位。

输入输出样例 1

5
8
10
3
11
1

3.0

说明/提示

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