题目描述

题目译自 Open Olympiad in Informatics 2023 Day2 T2 「Покупка подарков」。

小萨沙有两个女朋友，他想在三八妇女节为她们买礼物。为了这个目的，他前往了城市里最大的购物中心。

购物中心有 $n$ 个部门，每个部门恰好有两家商店。为了方便起见，我们将部门编号为从 $1$ 到 $n$ 的整数。已知第 $i$ 个部门的第一家商店的礼物价格为 $a_i$ 卢布，第二家商店的礼物价格为 $b_i$ 卢布。

进入购物中心后，萨沙会访问全部 $n$ 个部门，并且在每个部门中，他只会进入一家商店。因此，当萨沙到达第 $i$ 个部门时，他会执行以下两种操作之一：

1. 为第一个女朋友购买礼物，花费 $a_i$ 卢布。
2. 为第二个女朋友购买礼物，花费 $b_i$ 卢布。

萨沙计划为每个女朋友至少购买一个礼物。此外，他希望选择礼物，使得为两个女朋友购买的最贵礼物的价格差尽可能小，以免任何人感到不公平。

更形式化地，设 $m_1$ 为第一个女朋友收到礼物的最高价格，$m_2$ 为第二个女朋友收到礼物的最高价格。萨沙希望选择礼物，使 $\lvert m_1 - m_2 \rvert$ 的值最小化。

输入格式

第一行包含一个整数 $n$ $(2 \le n \le 500000)$，表示购物中心部门的个数。

接下来的 $n$ 行，每行包含两个整数 $a_i$ 和 $b_i$ $(0 \le a_i, b_i \le 10^{9})$，分别表示第 $i$ 个部门第一家和第二家商店的礼物价格。

输出格式

输出一个整数，即为两个女朋友购买的最贵礼物的最小价格差。

2
1 2
2 1

0

在第一个样例中，萨沙有两个选择：一种是在第一个部门为第一个女朋友买礼物，在第二个部门为第二个女朋友买礼物；另一种是反过来。在第一种情况下，$m_1 = m_2 = 1$，在第二种情况下，$m_1 = m_2 = 2$。两种情况下的答案均为 $0$。

5
1 5
2 7
3 3
4 10
2 5

1

在第二个样例中，可以在第 $2$、$4$ 和 $5$ 个部门为第一个女朋友购买礼物，在第 $1$ 和 $3$ 个部门为第二个女朋友购买礼物。这样，$m_1 = \max(2, 4, 2) = 4$，$m_2 = \max(5, 3) = 5$。答案为 $\lvert 4 - 5 \rvert = 1$。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。