Eng katta kesishma

Son o'qida $n$ ta kesma berilgan. Ulardan aynan bittasini olib tashlang, shunda qolgan $n - 1$ ta kesmaning umumiy kesishmasi uzunligi eng katta bo'lsin. Kesishma bo'sh yoki bitta nuqta bo'lsa, uzunligi $0$.

Birinchi qatorda $n$ ($2 \le n \le 3 \cdot 10^5$). Keyingi $n$ ta qatorda $l_i$ va $r_i$ ($0 \le l_i \le r_i \le 10^9$).

Bitta son — kesishmaning eng katta uzunligi.

Kesmalar kesishmasi — $[\max l, \min r]$, uzunligi $\max(0, \min r - \max l)$. $i$-kesmani olib tashlaganda qolganlarning $\max l$ va $\min r$ qiymatlari kerak. Chap uchlarni kamayish, o'ng uchlarni o'sish tartibida saralasangiz, eng katta ikki $l$ va eng kichik ikki $r$ yetadi: olib tashlangan kesma eng kattasini bergan bo'lsa, ikkinchisi olinadi. Boshqa usul — prefiks va suffiks bo'yicha maksimum/minimum.

Har bir kesmani olib tashlab qolganini qayta hisoblash $O(n^2)$ — vaqtga sig'maydi. Birinchi misolda $[0, 4]$ yoki $[2, 6]$ ni emas, $[3, 3]$ ni olib tashlash kerak: javob $3 - 2 = 1$.

Manba: Codeforces, 1029C-masala.