Blurred Pictures#9687
Damon enjoys photographing the places he visits during his travels and displaying the pictures in frames. All of his photographs have a square format of size n \times n pixels. During a trip to Paris, he took many beautiful photos of famous landmarks such as the Eiffel Tower and the Louvre; however, unfortunately, upon returning home he discovered that the edges of all his pictures were blurred.
After examining them more closely, Damon realized that blurred pixels are easy to distinguish from “good” (that is, non-blurred) ones. Moreover, all non-blurred pixels form a connected region with the property that any horizontal or vertical line drawn between two non-blurred pixels passes exclusively through non-blurred pixels.
In order to make the most of his unsuccessful photographs, Damon decides to cut out from each picture the largest possible image that contains no blurred pixels. Since all of his frames are square, for aesthetic reasons the cropped image must also be square. In addition, Damon does not want his photos to be tilted, so the sides of the cropped image must be parallel to the sides of the original photograph.
The first line contains a single integer n~(n \le 10^5) — the side length of the input image in pixels.
Each of the following lines contains two integers a_i and b_i~(0 \le a_i \le b_i < n) — the indices of the first (a_i) and the last (b_i) non-blurred pixels in the -th row.
It is guaranteed that:
Each row and each column of the input image contains at least one non-blurred pixel.
In any two adjacent rows, there are at least two non-blurred pixels located in the same column.
Print one integer — the side length of the largest square consisting entirely of non-blurred pixels inside the image.
Example 2
Example 1