Максимальное пересечение

На числовой прямой даны $n$ отрезков. Удалите ровно один из них так, чтобы длина общего пересечения оставшихся $n - 1$ отрезков была максимальной. Если пересечение пусто или является точкой, его длина $0$.

В первой строке $n$ ($2 \le n \le 3 \cdot 10^5$). В следующих $n$ строках $l_i$ и $r_i$ ($0 \le l_i \le r_i \le 10^9$).

Одно число — наибольшая длина пересечения.

Пересечение отрезков — $[\max l, \min r]$, его длина $\max(0, \min r - \max l)$. При удалении $i$-го отрезка нужны $\max l$ и $\min r$ остальных. Если отсортировать левые концы по убыванию, а правые по возрастанию, достаточно двух наибольших $l$ и двух наименьших $r$: если удалённый отрезок давал наибольшее значение, берётся второе. Другой способ — максимумы и минимумы на префиксах и суффиксах.

Пересчёт после удаления каждого отрезка — $O(n^2)$, это слишком долго. В первом примере нужно удалить не $[0, 4]$ и не $[2, 6]$, а $[3, 3]$: ответ $3 - 2 = 1$.

Источник: Codeforces, задача 1029C.