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_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 < \dots < 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 \le n \le 10^5$, and $0 \le x_1 < x_2 < \dots < x_{n-1} < x_n \le 10^9$.

Output

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