Snuke loves flags.
Snuke is placing $N$ flags on a line.
The $i$-th flag can be placed at either coordinate $x_i$ or coordinate $y_i$.
Snuke thinks that the flags look nicer when the smallest distance between two of them, $d$, is larger. Find the maximum possible value of $d$.
- $1≤x_i $ , $ y_i≤10^9$
- $x_i$ and $y_i$ are integers.
The input is given from Standard Input in the following format:
Print the answer.
The optimal solution is to place the first flag at coordinate 1, the second flag at coordinate 5 and the third flag at coordinate 9. The smallest distance between two of the flags is 4 in this case.
There can be more than one flag at the same position.