Gathering Place

　

The residents of Izua Village have decided to build a meeting place in their village. In this village, there are certain points where buildings can be built along the road in a straight line from east to west. The westernmost point is the 0th point, and from there the points are numbered evenly eastward: 1st, 2nd, and so on. It is only at these points that villagers can build their houses and meeting places. Each house has one or more villagers living in it. Any villager can travel to the next point in one minute.

To make it convenient to hold a meeting, we decided to build the meeting place in such a way that when all the villagers leave their houses at once at a certain time and head for the meeting place, the time required for everyone to gather will be minimized.

Given the numbers of the points where the house are built, create a program that calculates the minimum amount of time required for all the villagers to gather at the meeting place. Note that, it is assumed that the point number of the meeting place may overlap with the point number of the house.

Input

The input is given in the following form.

$N$
$x_1$ $x_2$ ... $x_N$

In the first line, the number of houses $N$ ($1 \leq N \leq 1000$) is given. In the second line, the point numbers where the house is built $x_i$ ($0 \leq x_i \leq 2000$) are given. Note that the point numbers of the houses are all different ($x_i \ne x_j$ for $i \ne j$).

Output

Output the minimum time (in minutes) required to gather at the meeting place on one line.

Sample Input and Output

Sample Input 1

3
4 0 1

Sample Output 1

2

Sample Input 2

2
1 2

Sample Output 2

1

---