You are planning a trip on a straight road
where locations are defined by its distance to some reference point.
The trip will start at x_{1},
it will pass through points x_{2}, …, x_{n−1} in this order,
and it will end at x_{n},
with x_{1} < x_{2} < … < x_{n−1} < x_{n}.
You will make exactly two stops, say at points x_{i} and x_{j}, with 1 < i < j < n.
You want to make the three distances x_{i} − x_{1}, x_{j} − x_{i} and x_{n} − x_{j}
as similar as possible.
More precisely, your goal is to minimize
the difference between the maximum and the minimum of those three distances.

For instance, supose a travel defined with 4 10 23 32 42 50. Here, the optimal choice is to stop at 23 and 32, which gives the distances 23 − 4 = 19, 32 − 23 = 9 and 50 − 32 = 18. In this case, the difference is 19 − 9 = 10. It is easy to see that we cannot make the difference smaller by choosing two other stopping points.

Input

Input consists of several cases.
Each case starts with n,
followed by x_{1}, …, x_{n}.
You can assume 4 ≤ n ≤ 10^{5},
and 0 ≤ x_{1} < x_{2} < … < x_{n−1} < x_{n} ≤ 10^{9}.

Output

For every case, print the minimum difference if we choose the optimal stops.

Public test cases

**Input**

6 4 10 23 32 42 50 4 0 200000000 700000000 1000000000 5 100000 240000 300000 500000 700000

**Output**

10 300000000 0

Information

- Author
- Salvador Roura
- Language
- English
- Official solutions
- C++
- User solutions
- C++