흐릿한 사진

Damon은 여행 중 방문한 장소를 사진으로 찍어 액자에 넣는 것을 좋아한다. 그가 가진 모든 사진은 N x N 픽셀의 정사각형 형식이다. 그는 파리의 여러 명소, 예를 들어 에펠탑이나 루브르 박물관을 찍은 아름다운 사진을 가지고 돌아왔지만, 집에 도착하고 나서 모든 사진의 가장자리가 흐릿해졌다는 사실을 알게 되었다. 자세히 살펴본 Damon은 흐릿한 픽셀과 "좋은" 즉 흐릿하지 않은 픽셀을 쉽게 구분할 수 있다는 것과, 다행히도 모든 흐릿하지 않은 픽셀이 연결되어 있어 두 흐릿하지 않은 픽셀 사이에 그은 수평선이나 수직선이 흐릿하지 않은 픽셀만을 지난다는 것을 깨달았다. 실패한 사진에서 최대한의 것을 얻기 위해 그는 각 사진에서 흐릿한 픽셀이 하나도 없는 가장 큰 사진을 잘라내기로 한다. 그리고 그의 액자가 모두 정사각형이므로 미적인 이유에서 잘라낸 사진도 정사각형이어야 한다. Damon은 사진이 기울어지기를 원하지 않으므로 잘라낸 사진의 변이 원본 사진의 변과 평행하기를 원한다.

입력은 여러 줄로 구성되며, 각 줄은 하나의 공백으로 구분된 정수로 이루어진다.

• 첫 번째 줄에는 입력 사진의 픽셀 단위 길이 N이 주어진다.
• 다음 N개 줄 각각에는 i번째 줄에서 흐릿하지 않은 첫 번째 픽셀의 인덱스 ai와 마지막 픽셀의 인덱스 bi가 주어진다.

출력은 한 줄로 구성되며, 그 내용은 사진 내부에서 흐릿하지 않은 픽셀로 이루어진 가장 큰 정사각형의 길이인 정수이다.

• 0 < N ≤ 100 000;
• 0 ≤ ai ≤ bi < N.

• 입력 사진에서 각 행과 각 열에는 흐릿하지 않은 픽셀이 적어도 하나 있다.
• 임의의 연속한 두 줄에서 같은 열에 흐릿하지 않은 픽셀이 적어도 두 개 있다.