配点 : $1200$ 点

問題文

すぬけくんは旗が好きです。

すぬけくんは $N$ 本の旗を一直線上に並べることにしました。

$i$ 番目の旗は座標 $x_i$ か座標 $y_i$ のどちらかに設置することができます。

すぬけくんは、$2$ つの旗同士の距離の最小値 $d$ が大きいほど、旗の並びの見栄えが良いと考えています。$d$ としてありうる値の最大値を求めなさい。

制約

• $2 \leq N \leq 10^{4}$
• $1 \leq x_i, y_i \leq 10^{9}$
• $x_i, y_i$ は整数

入力

入力は以下の形式で標準入力から与えられる。

$N$

$x_1$ $y_1$

$:$

$x_N$ $y_N$

出力

答えを出力せよ。

3
1 3
2 5
1 9

4

旗 $1$ を座標 $1$ に、旗 $2$ を座標 $5$ に、旗 $3$ を座標 $9$ に設置するのが最適であり、このとき旗同士の距離の最小値は $4$ となります。

5
2 2
2 2
2 2
2 2
2 2

0

旗の位置は重なることもあります。

22
93 6440
78 6647
862 11
8306 9689
798 99
801 521
188 206
6079 971
4559 209
50 94
92 6270
5403 560
803 83
1855 99
42 504
75 484
629 11
92 122
3359 37
28 16
648 14
11 269

17