Maximal intersection

You are given $n$ segments on a number line. Remove exactly one of them so that the length of the common intersection of the remaining $n - 1$ segments is as large as possible. An empty intersection or a single point has length $0$.

The first line contains $n$ ($2 \le n \le 3 \cdot 10^5$). The next $n$ lines contain $l_i$ and $r_i$ ($0 \le l_i \le r_i \le 10^9$).

A single number — the maximum length of the intersection.

The intersection of segments is $[\max l, \min r]$ with length $\max(0, \min r - \max l)$. When segment $i$ is removed, you need $\max l$ and $\min r$ of the others. If you sort the left ends in decreasing and the right ends in increasing order, the two largest $l$ and the two smallest $r$ are enough: if the removed segment gave the extreme value, take the second one. Another way is prefix and suffix maxima/minima.

Recomputing after removing each segment is $O(n^2)$ — too slow. In the first example you should remove $[3, 3]$, not $[0, 4]$ or $[2, 6]$: the answer is $3 - 2 = 1$.

Source: Codeforces, problem 1029C.