题目描述

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

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

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

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

输入格式

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

$N$ $x_1$ $y_1$ $:$ $x_N$ $y_N$

输出格式

答えを出力せよ。

题目大意

Snuke 将 $N$ 个标志放在一条线上。

第 $i$ 个标志可以放置在坐标 $x_i$ 或坐标 $y_i$ 上。

Snuke 认为当他们中的两个之间的最小距离 $d$ 更大时，标志看起来更好。找出 $d$ 的最大可能值。

感谢 @OrangeLee 提供的翻译。

3
1 3
2 5
1 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

提示

制約

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

Sample Explanation 1

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

Sample Explanation 2

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