题目描述

すぬけくん非常喜欢旗子。

他决定将 $N$ 面旗子沿着一条直线排列。

第 $i$ 面旗子可以放置在坐标 $x_i$ 或 $y_i$ 上。

すぬけくん认为，两面旗子之间的最小距离 $d$ 越大，旗子的排列看起来就越美观。请你求出所有可能的 $d$ 值中的最大值。

输入格式

输入通过标准输入给出，格式如下：

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

输出格式

请输出答案。

样例 1

输入

3
1 3
2 5
1 9

输出

4

样例 2

输入

5
2 2
2 2
2 2
2 2
2 2

输出

0

样例 3

输入

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 \leq N \leq 10^{4}$
• $1 \leq x_i, y_i \leq 10^{9}$
• $x_i, y_i$ 都是整数

样例解释 1

如果将第 $1$ 面旗子放在坐标 $1$，第 $2$ 面旗子放在坐标 $5$，第 $3$ 面旗子放在坐标 $9$，这样做是最优的，此时任意两面旗子的最小距离为 $4$。

样例解释 2

旗子的位置可以重合。

由 ChatGPT 5 翻译