{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/de1243f15b6712f9f1b9656b97575b1c?v\u003d1715438291\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e\u003cp\u003eDamon loves to take photos of the places he visits during his travels, to put them into frames. All of his photos are in a square format of $$$N \\times N$$$ pixels. He brought back beautiful pictures of the many monuments in Paris, such as the Eiffel Tower or the Louvre, but unfortunately, when he got back home, he realized that all his pictures were blurred on the edges. Looking closely, Damon realizes that he can easily distinguish the blurred pixels from the \"good\" (i.e., non-blurred) ones and that, luckily, all the non-blurred pixels are connected in such a way that any horizontal or vertical line drawn between two non-blurred pixels goes only through non-blurred pixels. In order to get the best from his failed pictures, he decides to cut out the biggest possible picture without any blurred pixel from each of his photos. And since his frames are all squares, for aesthetic reasons, the cut-out pictures have to be squares too. Damon does not want his pictures to be tilted so he wants the sides of the cut-outs to be parallel to the sides of the original picture.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe input comprises several lines, each consisting of integers separated with single spaces: \u003c/p\u003e\u003cul\u003e \u003cli\u003e The first line contains the length $$$N$$$, in pixels, of the input photo; \u003c/li\u003e\u003cli\u003e Each of the next $$$N$$$ lines contains two integers $$$a_i$$$ and $$$b_i$$$ , the indices of the first $$$(a_i)$$$ and the last $$$(b_i)$$$ non-blurred pixel on the $$$i$$$-th line. \u003c/li\u003e\u003c/ul\u003e \u003cul\u003e \u003cli\u003e $$$0 \u0026lt; N \\le 100000$$$, \u003c/li\u003e\u003cli\u003e $$$0\\le a_i\\le b_i \u0026lt; N$$$. \u003c/li\u003e\u003c/ul\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eThe output should consist of a single line, whose content is an integer, the length of the largest square composed of non-blurred pixels inside the picture.\u003c/p\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n1 1\n0 2\n1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e8\n2 4\n2 4\n1 4\n0 7\n0 3\n1 2\n1 2\n1 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cul\u003e \u003cli\u003e In the input picture, each row and each column has at least one non-blurred pixel. \u003c/li\u003e\u003cli\u003e In any two consecutive lines, there are at least two non-blurred pixels in the same column. \u003c/li\u003e\u003c/ul\u003e"}}]}