# Optimal trip P46672

Statement

thehtml

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 x1, it will pass through points x2, …, xn−1 in this order, and it will end at xn, with x1 < x2 < … < xn−1 < xn. You will make exactly two stops, say at points xi and xj, with 1 < i < j < n. You want to make the three distances xix1, xjxi and xnxj 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 x1, …, xn. You can assume 4 ≤ n ≤ 105, and 0 ≤ x1 < x2 < … < xn−1 < xn ≤ 109.

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