题目背景

CF1801B

题目描述

小萨沙有两位好朋友，他想在三八妇女节时为她们各自挑选礼物。为此，他来到了城市里最大的购物中心。

购物中心里有 $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$ 个部门两家商店礼物的价格。

输出格式

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

2
1 2
2 1

0

5
1 5
2 7
3 3
4 10
2 5

1

提示

样例解释

在第一个样例中，萨沙有两种选择：在第一个部门为第一位朋友买礼物，在第二个部门为第二位朋友买礼物，或者反过来。在这两种情况下，$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 组。只有通过某一组的所有测试点，且通过部分之前组的所有测试点，才能获得该组分数。

组别	分值	$n$	$a_i$ 和 $b_i$	必须通过的组	备注
0		--	--	--	样例测试点
1	16	$n \le 20$		0	--
2	17	$n \le 500$		0, 1
3	22	$n \le 5000$		0, 1, 2
4	12	--	$a_i = b_i$	--
5	33		--	0--4