C. Максимальное пересечение
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Заданы $$$n$$$ отрезков на числовой прямой; границы каждого отрезка имеют целочисленные координаты. Некоторые отрезки могут вырождаться в точки. Отрезки могут пересекаться, вкладываться друг в друга или даже совпадать.

Пересечение некоторой последовательности отрезков — это такое максимальное по включению множество точек (не обязательно имеющих целые координаты), что каждая точка лежит внутри каждого отрезка из последовательности. Если полученное множество не пусто, то оно всегда образует некоторый непрерывный отрезок. Длина пересечения — это длина полученного отрезка, либо $$$0$$$, если пересечение — пустое множество.

Например, пересечение отрезков $$$[1;5]$$$ и $$$[3;10]$$$ — это $$$[3;5]$$$ (длина $$$2$$$), пересечение отрезков $$$[1;5]$$$ и $$$[5;7]$$$ — это $$$[5;5]$$$ (длина $$$0$$$) и пересечение отрезков $$$[1;5]$$$ и $$$[6;6]$$$ — это пустое множество (длина $$$0$$$).

Ваша задача — удалить ровно один отрезок из заданной последовательности таким образом, чтобы пересечение оставшихся $$$(n - 1)$$$ отрезков имело максимальную длину.

Входные данные

В первой строке записано одно целое число $$$n$$$ ($$$2 \le n \le 3 \cdot 10^5$$$) — количество отрезков в последовательности.

В каждой следующих $$$n$$$ строк записаны по два целых числа $$$l_i$$$ и $$$r_i$$$ ($$$0 \le l_i \le r_i \le 10^9$$$) — описание $$$i$$$-го отрезка.

Выходные данные

Выведите одно целое число — максимально возможную длину пересечения $$$(n - 1)$$$ отрезка после удаления ровно одного отрезка из последовательности.

Примеры
Входные данные
4
1 3
2 6
0 4
3 3
Выходные данные
1
Входные данные
5
2 6
1 3
0 4
1 20
0 4
Выходные данные
2
Входные данные
3
4 5
1 2
9 20
Выходные данные
0
Входные данные
2
3 10
1 5
Выходные данные
7
Примечание

В первом примере необходимо удалить отрезок $$$[3;3]$$$, пересечение станет $$$[2;3]$$$ (длина $$$1$$$). Удаление любого другого отрезка приведет к пересечению $$$[3;3]$$$ (длина $$$0$$$).

Во втором примере необходимо удалить отрезок $$$[1;3]$$$ или отрезок $$$[2;6]$$$, пересечение станет $$$[2;4]$$$ (длина $$$2$$$) или $$$[1;3]$$$ (длина $$$2$$$), соответственно. Удаление любого другого отрезка приведет к пересечению $$$[2;3]$$$ (длина $$$1$$$).

В третьем примере пересечение станет пустым множеством вне зависимости от удаленного отрезка.

В четвертом примере вы получите пересечение $$$[3;10]$$$ (длина $$$7$$$) после удаления отрезка $$$[1;5]$$$ или же пересечение $$$[1;5]$$$ (длина $$$4$$$) после удаления отрезка $$$[3;10]$$$.