Злые коровы (Золото)

Беси придумала игру. Игрок бросает корову на одномерную сцену, состоящую из множества стогов сена, расположенных в различных точках числовой прямой. После приземления коровы может возникнуть цепная реакция взрывов. Цель - используя одну корову, начать цепную реакцию так, чтобы взорвать все стоги сена.

Имеется n стогов сена, расположенных в различных целочисленных позициях x[1], x[2], ..., x[n] на числовой прямой. Если корова приземлится с энергией r в позиции x, это вызовет взрыв "радиусом r", что вызовет взрывы всех стогов сена в диапазоне x − r ... x + r. Все стоги сена в этом диапазоне также одновременно взрываются с радиусом взрыва r − 1. Все ещё не взорванные стоги сена, попавшие в этот диапазон, снова взрываются уже с радиусом взрыва r − 2, и т.д.

Определите минимальное количество энергии r, с которым должна приземлиться корова, так что если она приземлится в оптимальном положении, то взорвутся все стоги сена на сцене.

Входные данные

Первая строка содержит n (2 ≤ n ≤ 50000). Оставшиеся n строк содержат целые числа x[1] ... x[n] (каждое в диапазоне 0 ... 10^9).

Выходные данные

Выведите минимальную энергию R, с которой должна приземлится корова, для того, чтобы взорвать все стоги сена. Ответ округлить и вывести с одним знаком после десятичной точки.

Примеры

Примечание

В этом примере, корова приземлившись с энергией 3 в позиции 5, вызовет взрывы стогов сена в позициях 3 и 8, затем взрывы будут с радиусом 2, охватив позиции 1 и 10, которые вызовут взрывы радиуса 1, взрывая последний стог сена в позиции 11, которая взрывается с радиусом 0.