题目描述

Snuke喜欢旗帜。

Snuke要在一条线上放置$N$面旗帜。

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

Snuke认为，两面旗帜之间的最小距离$d$越大，旗帜看起来就越漂亮。找到$d$的最大可能值。

约束条件

• $2 ≤ N ≤ 10^{4}$
• $1 ≤ x_i, y_i ≤ 10^{9}$
• $x_i$和$y_i$是整数。

输入

从标准输入读入输入数据，格式如下：

$N$

$x_1$ $y_1$

$:$

$x_N$ $y_N$

输出

打印答案。

示例输入 1

3
1 3
2 5
1 9

示例输出 1

4

最优解是将第一面旗帜放置在坐标$1$，第二面旗帜放置在坐标$5$，第三面旗帜放置在坐标$9$。在这种情况下，两面旗帜之间的最小距离是$4$。

示例输入 2

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

示例输出 3

17