### 问题描述 大衣有 $N$ 个整数对，第 $i$ 对为 $(A_i,B_i)$。 大衣给你两个空袋子，它们最初都是空的，你可以进行以下操作： - 对于从 $1$ 到 $N$ 的每一个整数对，选择 $A_i$ 和 $B_i$ 中的其中一个。 - 然后将选择的元素放入到两个袋子其中一个内。 在完成所有操作后，要求两个袋子都必须是非空的。 袋子的值定义为袋子中最大元素的值，大衣想让你以最佳方式进行操作，使得两个袋子的值之间的差值尽可能小，你能求出最小差值吗？ ### 输入格式 第一行输入一个正整数 $N$ 表示整数对的个数。 接下来 $N$ 行每行输入两个正整数 $A_i$ 和 $B_i$ 表示第 $i$ 对元素。 ### 输出格式 输出一个整数表示两个袋子的值之间的最小差值。 ### 样例输入1 ```text 2 1 6 4 9 ``` ### 样例输出1 ```text 2 ``` ### 样例输入2 ```text 2 1 9 4 6 ``` ### 样例输出2 ```text 3 ``` ### 样例输入3 ```text 4 10 10 23 55 21 80 105 91 ``` ### 样例输出3 ```text 11 ``` ### 说明 - 样例 $1$：两对元素分别为 $(1,6)$ 和 $(4,9)$，选择第 $1$ 对中的元素 $6$ 和第 $2$ 对中的元素 $4$ 分别放在两个袋子中，得到两个袋子的值之间的最小差值为 $|6-4|=2$。 - 样例 $2​$：两对元素分别为 $(1,9)​$ 和 $(4,6)​$，选择第 $1​$ 对中的元素 $9​$ 和第 $2​$ 对中的元素 $6​$ 分别放在两个袋子中，得到两个袋子的值之间的最小差值为 $|9-6|=3​$。 - 样例 $3$：一种选择方法如下： - 选择第 $1$ 对中的元素 $10$ 放在第一个袋子。 - 选择第 $2$ 对中的元素 $55$ 放在第二个袋子。 - 选择第 $3$ 对中的元素 $80$ 放在第二个袋子。 - 选择第 $4$ 对中的元素 $91$ 放在第一个袋子。 此时两个袋子的值之间的差值为 $|80-91|=11​$，没有比这个更小的差值。 ### 评测数据规模 对于所有的评测数据，$1\le N\le 2\times10^5$，$1\le A_i,B_i\le10^9​$。