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 цифры после десятичной точки.

Примеры

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

5
8
10
3
11
1

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

3.0

Примечание

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

Автор задачи: Brian Dean