读写要求

本题采用文件读写，请在提交代码时使用正确的文件读写方式，否则会导致 RE

输入：jump.in

输出：jump.out

题目描述

珀利卡普正在为一个游戏设计关卡。这个关卡由数轴上的 $n$ 个区间组成，第 $i$ 个区间的起点为 $l_i$，终点为 $r_i$。

玩家从坐标 $0$ 处开始。在一次移动中，玩家可以移动到距离当前位置不超过 $k$ 的任意点。在第 $i$ 次移动后，玩家必须停在第 $i$ 个区间内，即坐标 $x$ 满足 $l_i \le x \le r_i$。具体来说：

• 第一次移动后，玩家必须在第一个区间（$l_1$ 到 $r_1$）内；
• 第二次移动后，玩家必须在第二个区间（$l_2$ 到 $r_2$）内；
• ...
• 第 $n$ 次移动后，玩家必须在第 $n$ 个区间（$l_n$ 到 $r_n$）内。

如果玩家按照上述规则到达第 $n$ 个区间，则视为完成关卡。珀利卡普发现，对于某些 $k$ 的取值，关卡无法完成。

珀利卡普不希望关卡太简单，因此他希望你求出能够完成关卡的最小整数 $k$。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示关卡中的区间数量。

接下来的 $n$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$0 \le l_i \le r_i \le 10^9$），表示第 $i$ 个区间的左右端点。区间可能有重叠。

$n$ 不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出一个整数，表示能够完成关卡的最小 $k$。

输入输出样例

5
1 5
3 4
5 6
8 10
0 1

3
0 2
0 1
0 3

3
3 8
10 18
6 11

4
10 20
0 5
15 17
2 2

7

0

5

13

说明/提示

在第三个样例中，玩家可以按如下方式移动：

• 从 $0$ 移动到 $5$（$3 \le 5 \le 8$）；
• 从 $5$ 移动到 $10$（$10 \le 10 \le 18$）；
• 从 $10$ 移动到 $7$（$6 \le 7 \le 11$）。

注意，最后一步玩家也可以选择不移动，依然可以完成关卡。