## USACO 2016 January Contest, Gold

## Problem 1. Angry Cows

Contest has ended.

**Log in to allow submissions in analysis mode**

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.

#### INPUT FORMAT (file angry.in):

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$).#### OUTPUT FORMAT (file angry.out):

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.#### SAMPLE INPUT:

5 8 10 3 11 1

#### SAMPLE OUTPUT:

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.

Problem credits: Brian Dean