Optimal trip P46672

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₁, it will pass through points x₂, …, x_n−1 in this order, and it will end at x_n, with x₁ < x₂ < … < 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₁, 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₁, …, x_n. You can assume 4 ≤ n ≤ 10⁵, and 0 ≤ x₁ < x₂ < … < x_n−1 < x_n ≤ 10⁹.

Output

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