说明

Damon 喜欢为他旅行中所到之处拍摄照片，并将它们装入相框。他所有的照片都是 $N \times N$ 像素的正方形格式。他从巴黎带回了许多纪念碑（如埃菲尔铁塔或卢浮宫）的美丽照片，但不幸的是，当他回到家时，他发现所有照片在“好”（即非模糊）的部分都模糊了，而且幸运的是，所有非模糊像素的连接方式使得任意两个非模糊像素之间绘制的水平线或垂直线只经过非模糊像素。为了从他失败的照片中获取最佳效果，他决定从每张照片中切割出可能最大的、不含任何模糊像素的图片。由于他的相框都是正方形的，出于美观原因，切割出的图片也必须是正方形。Damon 不希望他的图片倾斜，因此要求切割出的正方形的边与原始图片的边平行。

重要提示

• 在输入图片中，每行和每列至少有一个非模糊像素。
• 在任何连续两行中，至少有两列有非模糊像素。

输入格式

输入包含若干行，每行由空格分隔的整数组成：

• 第一行包含输入照片的像素长度 $N$；
• 接下来的 $N$ 行每行包含两个整数 $a_i$ 和 $b_i$，表示第 $i$ 行第一个非模糊像素的索引 $a_i$ 和最后一个非模糊像素的索引 $b_i$。

输出格式

输出应包含一行，内容为一个整数，表示图片中由非模糊像素组成的最大正方形的边长。

3
1 1
0 2
1 1

1

8
2 4
2 4
1 4
0 7
0 3
1 2
1 2
1 1

3

提示

数据范围

• $0 < N \leq 100\,000$；
• $0 \leq a_i \leq b_i < N$。

翻译由 DeepSeek 完成