题目描述

彼得罗夫的课表里面有很多课，这些课可以视为 $n$ 个时间段，每个时间段给出的形式为 $\{a,b\}$。其中 $a,b$ 为两个整数，分别表示时间段的起始和结束时刻，保证结束时刻总在开始时刻之后。彼得罗夫发现这些课的时间可能会冲突，请你帮彼得罗夫找到交集时间最长的两个时间段的交集时间。

输入格式

第一行一个非负整数 $n$。

接下来 $n$ 行，每行两个整数 $a_i$ 和 $b_i$。

输出格式

一行一个整数，表示最长冲突时间。如果不存在冲突，输出 $0$。

5
800 1000
1000 1200
900 1100
200 950
750 800

150

提示

对于 $40\%$ 的数据，满足 $n=2$。

对于额外 $20\%$ 的数据，满足 $n\le 10$。

对于额外 $20\%$ 的数据，满足 $a_i\le b_i\le 50$。

对于 $100\%$ 的数据，满足 $2\le n\le 1000,a_i\le b_i<2400$。