[Poi2011]Temperature

比特王国气象研究所每天都会自动测量并打印气温，但由于打印机的墨水早已干涸，研究所未能保存这些测量结果。

幸运的是，实习生 Byteasar 每天都记录了研究所大楼南墙和北墙上两支温度计的读数。根据长期观察，南墙温度计的读数不会低于实际温度，北墙温度计的读数不会高于实际温度。因此，虽然无法确定每天的准确气温，但可以确定第 $i$ 天的实际气温位于区间 $[l_i,r_i]$ 内。

现在需要找出一段尽可能长的连续日期，使得可以从每天对应的区间中各选取一个实际气温，并使这段日期内的气温单调不降。也就是说，若所选气温依次为 $t_a,t_{a+1},\ldots,t_b$，则需要满足：

$$l_i\le t_i\le r_i$$

且

$$t_a\le t_{a+1}\le\cdots\le t_b。$$

请计算满足条件的最长连续日期段的长度。

输入格式

第一行包含一个整数 $n$，表示记录气温的天数。

接下来 $n$ 行，第 $i$ 行包含两个整数 $l_i,r_i$，表示第 $i$ 天实际气温的可能范围为 $[l_i,r_i]$。

输出格式

输出一个整数，表示气温可能单调不降的最长连续日期段的长度。

样例输入

6

6 10

1 5

4 8

2 5

6 8

3 5

样例输出

4

数据范围

• $1\le n\le 10^6$；
• $-10^9\le l_i\le r_i\le 10^9$；
• 部分测试数据共计 $50$ 分，满足 $-50\le l_i\le r_i\le 50$；
• 时间限制为 $2\times 10^4\ \mathrm{ms}$；
• 内存限制为 $32768\ \mathrm{KB}$。

来源与许可

本题为 POI 2011 试题「Temperature」，题面与测试数据整理自 BZOJ 2276。

样例 1

输入

6

6 10

1 5

4 8

2 5

6 8

3 5

输出

4