# [Usaco2016 Jan]Angry Cows

时间限制：10s 空间限制：128MB

### 题目描述

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 NN hay bales located at distinct integer positions x1,x2,…,xNx1,x2,…,xN on the number line. If a cow is launched with power RR landing at position xx, this will causes a blast of "radius RR", engulfing all hay bales within the range x−R…x+Rx−R…x+R. These hay bales then themselves explode (all simultaneously), each with a blast radius of R−1R−1. Any not-yet-exploded bales caught in these blasts then all explode (all simultaneously) with blast radius R−2R−2, and so on.

Please determine the minimum amount of power RR 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 NN (2≤N≤50,000). The remaining NN lines all contain integers x1…xN (each in the range 0…1,000,000,000).

### 输出格式

Please output the minimum power RR 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.

### 样例输入

5 8 10 3 11 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.

### 提示

没有写明提示

### 题目来源

Gold