CF1801B Buying gifts

可以在 [P13532](https://www.luogu.com.cn/problem/P13532) 评测本题。

小萨沙有两位好朋友，他想在三八妇女节时为她们各自挑选礼物。为此，他来到了城市里最大的购物中心。 购物中心里有 $n$ 个部门，每个部门里恰好有两家商店。我们用 $1$ 到 $n$ 给这些部门编号。已知第 $i$ 个部门的第一家商店的礼物价格为 $a_i$ 卢布，第二家商店的礼物价格为 $b_i$ 卢布。 进入购物中心后，萨沙会依次经过所有 $n$ 个部门，并且在每个部门里只会进入一家商店。因此，在第 $i$ 个部门，他会做如下两种选择之一： 1. 为第一位朋友购买礼物，花费 $a_i$ 卢布。 2. 为第二位朋友购买礼物，花费 $b_i$ 卢布。 对于每位朋友，萨沙都要至少买一个礼物。此外，他还希望选择礼物的方式，使得两位朋友收到的最贵礼物的价格之差尽可能小，这样谁都不会觉得不公平。 更具体地说，设 $m_1$ 为第一位朋友收到的礼物中最贵的价格，$m_2$ 为第二位朋友收到的礼物中最贵的价格。萨沙想要最小化 $| m_1 - m_2 |$。

第一行包含一个整数 $n$（$2 \le n \le 500\,000$），表示购物中心的部门数。 接下来的 $n$ 行，每行两个整数 $a_i$ 和 $b_i$（$0 \le a_i, b_i \le 10^9$），分别表示第 $i$ 个部门两家商店礼物的价格。

输出一个整数，表示两位朋友收到的最贵礼物价格的最小差值。

### 样例解释 在第一个样例中，萨沙有两种选择：在第一个部门为第一位朋友买礼物，在第二个部门为第二位朋友买礼物，或者反过来。在这两种情况下，$m_1 = m_2 = 1$ 或 $m_1 = m_2 = 2$，结果都是 $0$。 在第二个样例中，可以在第 $2$、$4$、$5$ 个部门为第一位朋友买礼物，在第 $1$、$3$ 个部门为第二位朋友买礼物。此时 $m_1 = \max(2, 4, 2) = 4$，$m_2 = \max(5, 3) = 5$，答案为 $|4 - 5| = 1$。