Shortest Board Length to Cover Holes

The two boards must have the same positive integer length L; a board placed at X covers the closed interval [X,X+L]. Find the minimum L needed to cover all distinct hole coordinates. The boards may overlap, and one of them may cover no hole.

输入格式

The first line contains N (1..100000), and the second line contains N distinct coordinates (0..10⁹), possibly unsorted.

输出格式

Output a single integer, the answer.

样例 1

输入：

3
11 20 15

输出：

4

样例 2

输入：

4
15 20 9 11

输出：

5

样例 3

输入：

1
9

输出：

1

样例说明

Example 1: one board covers 11..15 and the other covers 20, so the minimum length is 4.

Example 2: split the holes into 9..11 and 15..20; the larger span is 5, so the answer is 5.

Example 3: even with only one hole the length must be positive, so the answer is 1.