#1420. 川川的秘密日记

内存限制:512 MiB 时间限制:2500 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: MCPlayer542

题目描述

LmfLrf的一堆东西里发现了一个本子,封面写着《川川的秘密日记》:

2023年1月25日 星期三 晴

czq告诉我他脱单了。
太棒了,以后他终于不会再缠着我发电了。


2023年3月24日 星期五 小雨

晚上hrj穿着[模糊不清]躺在旁边看我打老头环。
算了,明天是EC Final,忍一忍就过去了。

Lmf一眼就看出这个日记里记录着Lrf和他的许多前男友(迫真)的故事。她统计了日记中每个人的第一次出现时间和最后一次出现时间,并认为这就是Lrf可能与之交往的最早和最晚的时间。

并且,Lmf还发现,对任意两个人,若的第一次出现比更早,则的最后一次出现一定不会比更晚。即,对任意,或

现在Lmf非常生气,她想让你求出,Lrf和所有前男友交往的连续时长中最短时长最大是多少。

注意Lrf非常专一,所以他同一时间只能有一个男朋友;但是,他可以多次和同一个男孩子交往。

输入格式

第一行一个数,表示曾经有个群友对Lrf发过电Lrf可能有个前男友。

接下来行,每行两个数,表示第个人在日记中第一次和最后一次出现的时刻。

保证,满足,或

输出格式

一个数,表示Lrf和所有前男友交往的最短连续时长的最大值。

样例

样例输入1

5
18 20
11 16
8 13
5 8
13 19

样例输出1

3

样例输入2

10
79 91
65 84
43 57
18 51
81 93
59 79
59 80
85 97
78 89
70 87

样例输出2

4

数据范围与提示

在样例1中,Lrf可以分别在时间单位区间内分别和每个男孩子交往,交往时长分别为,故在这个方案中连续时长的最小值为。又因为跟第一个男孩子最多只能交往个时间单位,故不存在能使得连续时长最小值更大的方案。