Розмиті картинки#9687
Деймон любить фотографувати місця, які він відвідує під час своїх подорожей, щоб потім поміщати знімки в рамки. Усі його фотографії мають квадратний формат розміром n \times n пікселів. Під час поїздки до Парижа він зробив багато красивих фотографій відомих пам’яток, таких як Ейфелева вежа і Лувр, однак, на жаль, повернувшись додому, він виявив, що краї всіх його знімків виявилися розмитими.
Придивившись уважніше, Деймон зрозумів, що розмиті пікселі легко відрізнити від «хороших» (тобто нерозмитих). Більше того, всі нерозмиті пікселі утворюють зв’язну область з тією властивістю, що будь-яка горизонтальна або вертикальна лінія, проведена між двома нерозмитими пікселями, проходить виключно через нерозмиті пікселі.
Щоб витягти максимум з невдалих фотографій, Деймон вирішує вирізати з кожного знімка найбільше можливе зображення, яке не містить розмитих пікселів. Оскільки всі його рамки мають квадратну форму, з естетичних міркувань вирізане зображення також має бути квадратним. Крім того, Деймон не хоче, щоб фотографії були нахилені, тому сторони вирізаного зображення повинні бути паралельні сторонам вихідної фотографії.
Перша строка містить ціле число n~(n \le 10^5) — довжину сторони вхідного зображення в пікселях;
Кожна з наступних рядків містить два цілі числа a_i та b_i~(0 \le a_i \le b_i < n) — індекси першого (a_i) та останнього (b_i) нерозмитих пікселів у -му рядку.
Відомо, що:
У кожному рядку і в кожному стовпці вхідного зображення міститься як мінімум один нерозмитий піксель.
У будь-яких двох сусідніх рядках існує як мінімум два нерозмитих пікселі, розташованих в одному і тому ж стовпці.
Виведіть одне ціле число — довжину сторони найбільшого квадрата, повністю складеного з нерозмитих пікселів усередині зображення.
Приклад 2
Приклад 1