题目描述

Bob 有 $n$ 个数对，第 $i$ 个是 $(a_i,b_i)$，同时有两个桶，初始都为空。

Bob 会对于 $i=1,2,\cdots,n$，依次选择 $a_i,b_i$ 中的恰好一个，并任意加入到他的任意一个桶中。

最终，Bob 的两个桶里必须都非空，他想要最小化两个桶中最大元素的差值，请求出这个值。

输入输出格式

输入格式

第一行一个整数 $n$。

接下来 $n$ 行，每行两个整数 $a_i,b_i$ 表示一个数对。

输出格式

一行一个整数表示答案。

输入输出样例

2
1 6
4 9

2

2
1 9
4 6

3

样例解释

样例 1 解释：

在 (1,6) 中选择 6 放入桶 1
在 (4,9) 中选择 4 放入桶 2
两个桶最大元素的差值为 6-4=2。

样例 2 解释：

在 (1,9) 中选择 9 放入桶 1
在 (4,6) 中选择 6 放入桶 2
两个桶最大元素的差值为 9-6=3。

数据范围

对于 $30\%$ 的数据，$n\leq 18$。

对于 $60\%$ 的数据，$n\leq 1000$。

对于 $100\%$ 的数据，$2\leq n\leq 2\times 10^5$，$1\leq a_i,b_i\leq 10^9$。