Angry Cows

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 off a chain reaction that causes additional hay bales to explode. 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\), it produces a blast of radius \(R\) that engulfs 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 hay bales caught in these blasts then all explode (all simultaneously) with blast radius \(R-2\), and so on. The goal is to 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 a chain reaction that detonates every single hay bale in the scene.

inputFormat

The first line contains a single integer \(N\) representing the number of hay bales. The second line contains \(N\) distinct integers \(x_1, x_2, \ldots, x_N\) separated by spaces, indicating the positions of the hay bales on the number line.

outputFormat

Output a single integer, the minimum power \(R\) required to detonate all hay bales.

sample

3
1 3 6

3