在数轴上给你 $$$n$$$ 线段;每个线段的每个端点都有整数坐标。有些段可以退化为点。线段可以相互交叉、相互嵌套甚至重合。
线段序列的交集是最大的点集(不一定具有整数坐标),使得每个点都位于序列中的每个线段内。如果结果集不为空,那么它总是形成一些连续的段。交集的长度是结果线段的长度,如果交集是空集,则为 $$$0$$$。
例如,线段 $$$[1;5]$$$ 和 $$$[3;10]$$$ 的交集是 $$$[3;5]$$$(长度 $$$2$$$),线段 $$$[1;5]$$$ 和 $$$[5;7]$$$ 的交集是 $$$[5;5]$$$(长度 $$$0$$$)并且交集段 $$$[1;5]$$$ 和 $$$[6;6]$$$ 是一个空集(长度 $$$0$$$)。
您的任务是从给定序列中恰好删除一个段,以使剩余 $$$(n - 1)$$$ 段的交集具有最大可能长度。
输入
第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — 序列中的段数。
接下来的 $$$n$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$) — 第 $$$i$$$ 段的描述。
输出
打印一个整数 — 从序列中删除一个片段后 $$$(n - 1)$$$ 剩余片段的交集的最大可能长度。
示例
输入 #1
4 1 3 2 6 0 4 3 3
输出 #1
1
输入 #2
5 2 6 1 3 0 4 1 20 0 4
输出 #2
2
输入 #3
3 4 5 1 2 9 20
输出 #3
0
输入#4
2 3 10 1 5
输出#4
7
注意
在第一个示例中,您应该删除线段$$$[3;3]$$$,交集将变为$$$[2;3]$$$(长度$$$1$$$)。删除任何其他线段将导致交集 $$$[3;3]$$$(长度 $$$0$$$)。
在第二个示例中,您应该删除线段 $$$[1;3]$$$ 或线段 $$$[2;6]$$$,交集将分别变为 $$$[2;4]$$$ (长度 $$$2$$$)或 $$$[1;3]$$$ (长度 $$$2$$$)。删除任何其他线段将导致交集 $$$[2;3]$$$(长度 $$$1$$$)。
在第三个示例中,无论您删除哪条线段,交集都将变为空集。
在第四个示例中,如果删除段 $$$[1;5]$$$,您将获得交集 $$$[3;10]$$$(长度 $$$7$$$);如果删除段 $$$[3;10]$$$,您将获得交集 $$$[1;5]$$$(长度 $$$4$$$)。