Damon 喜欢在他旅行时拍摄照片，并将它们放入相框中。他所有的照片都是 $N \times N$ 像素的方形格式。他带回了许多巴黎古迹的美丽照片，例如埃菲尔铁塔或卢浮宫，但不幸的是，当他回到家时，他发现他所有的照片边缘都模糊了。仔细观察后，Damon 意识到他可以很容易地将模糊的像素与“好的”（即非模糊的）像素区分开来，而且幸运的是，所有非模糊像素的连接方式使得任意两个非模糊像素之间所画的水平线或垂直线都只经过非模糊像素。为了从他失败的照片中获得最好的效果，他决定从每张照片中剪裁出不包含任何模糊像素的最大可能图片。由于他的相框都是正方形的，出于美观考虑，剪裁出的图片也必须是正方形。Damon 不希望他的照片倾斜，因此他希望剪裁出的图片边与原图的边平行。

重要说明

• 在输入图片中，每一行和每一列至少有一个非模糊像素。
• 在任意两行相邻的行中，同一列中至少有两个非模糊像素。

输入格式

输入包含多行，每行由以空格分隔的整数组成： 第一行包含输入照片的边长 $N$（以像素为单位）； 接下来的 $N$ 行，每行包含两个整数 $a_i$ 和 $b_i$，分别表示第 $i$ 行第一个非模糊像素的索引 ($a_i$) 和最后一个非模糊像素的索引 ($b_i$)。

数据范围

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

输出格式

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

样例

样例输入 1

3
1 1
0 2
1 1

样例输出 1

1

样例输入 2

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

样例输出 2

3