小 Sasha 有两位女性朋友，他想在三八妇女节送礼物给她们。为此，他前往了城里最大的购物中心。

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

进入购物中心后，Sasha 将会拜访全部 $n$ 个部门，且在每个部门中他恰好会进入其中一家商店。因此，当 Sasha 到达第 $i$ 个部门时，他会执行以下两个操作之一：

• 给第一位朋友买一件礼物，花费 $a_i$ 卢布。
• 给第二位朋友买一件礼物，花费 $b_i$ 卢布。

Sasha 打算给每位朋友都至少买一件礼物。此外，他希望选择礼物，使得送给两位朋友的最贵礼物价格之差尽可能小，以免有人感到委屈。

更正式地：设 $m_1$ 为买给第一位朋友的礼物的最大价格，$m_2$ 为买给第二位朋友的礼物的最大价格。Sasha 希望选择礼物以最小化 $|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$ 个部门中第一家和第二家商店的礼物价格。

输出格式

输出一个整数 —— 买给两位朋友的最贵礼物价格之差的最小值。

样例

输入样例 1

2
1 2
2 1

输出样例 1

0

输入样例 2

5
1 5
2 7
3 3
4 10
2 5

输出样例 2

1

说明

在第一个样例中，Sasha 有两种可能的选择：在第一个部门给第一位朋友买礼物，在第二个部门给第二位朋友买礼物；或者反过来。在第一种情况下，$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$。

子任务

本题的测试点分为 5 个子任务。只有通过该子任务的所有测试点以及某些指定的前置子任务的所有测试点，才能获得该子任务的分数。