시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 181 58 39 35.135%

## 문제

Bessie the cow has designed what she thinks will be the next big hit video game: "Angry Cows". The premise, which she believes is completely original, is that the player shoots a cow with a slingshot into a one-dimensional scene consisting of a set of hay bales located at various points on a number line; the cow lands with sufficient force to detonate the hay bales in close proximity to her landing site, which in turn might set of a chain reaction that causes additional hay bales to explode. The goal is to use a single cow to start a chain reaction that detonates all the hay bales.

There are $$N$$ hay bales located at distinct integer positions $$x_1, x_2, \ldots, x_N$$ on the number line. If a cow is launched with power $$R$$ landing at position $$x$$, this will causes a blast of "radius $$R$$", engulfing all hay bales within the range $$x-R \ldots x+R$$. These hay bales then themselves explode (all simultaneously), each with a blast radius of $$R-1$$. Any not-yet-exploded bales caught in these blasts then all explode (all simultaneously) with blast radius $$R-2$$, and so on.

Please determine the minimum amount of power $$R$$ with which a single cow may be launched so that, if it lands at an appropriate location, it will cause subsequent detonation of every single hay bale in the scene.

## 입력

The first line of input contains $$N$$ ($$2 \leq N \leq 50,000$$). The remaining $$N$$ lines all contain integers $$x_1 \ldots x_N$$ (each in the range $$0 \ldots 1,000,000,000$$).

## 출력

Please output the minimum power $$R$$ with which a cow must be launched in order to detonate all the hay bales. Answers should be rounded and printed to exactly 1 decimal point.

## 예제 입력 1

5
8
10
3
11
1


## 예제 출력 1

3.0


## 힌트

In this example, a cow launched with power 3 at, say, location 5, will cause immediate detonation of hay bales at positions 3 and 8. These then explode (simultaneously) each with blast radius 2, engulfing bales at positions 1 and 10, which next explode (simultaneously) with blast radius 1, engulfing the final bale at position 11, which finally explodes with blast radius 0.