Беси придумала игру.
Игрок бросает корову на одномерную сцену, состоящую из множества стогов сена,
расположенных в различных точках числовой прямой. После приземления коровы
может возникнуть цепная реакция взрывов. Цель - используя одну корову,
начать цепную реакцию так, чтобы взорвать все стоги сена.
Имеется \(N\) стогов сена, расположенных в различных целочисленных позициях
\(x_1, x_2, \ldots, x_N\) на числовой прямой. Если корова приземлится с энергией \(R\)
в позиции \(x\), это вызовет взрыв "радиусом \(R\)", что вызовет
взрывы всех стогов сена в диапазоне \(x-R \ldots x+R\). Все стоги сена в этом
диапазоне также одновременно взрываются с радиусом взрыва \(R-1\). Все ещё не взорванные
стоги сена, попавшие в этот диапазон, снова взрываются уже с радиусом взрыва \(R-2\),
и т.д.
Пожалуйста, определите минимальное количество энергии \(R\), с которым должна
приземлиться корова, так что если она приземлится в оптимальном положении, то
взорвутся все стоги сена на сцене.
ФОРМАТ ВВОДА (файл angry.in):
Первая строка ввода содержит \(N\) (\(2 \leq N \leq 50,000\)). Оставшиеся \(N\)
строк содержат целые числа \(x_1 \ldots x_N\) (каждое в диапазоне \(0 \ldots 1,000,000,000\)).
ФОРМАТ ВЫВОДА (файл angry.out):
Выведите минимальную энергию \(R\), с которой должна приземлится корова, для
того, чтобы взорвать все стоги сена. Ответ округлить и вывести с одним знаком
после десятичной точки.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8
10
3
11
1
|
3.0
|