Problem:
 Score : 600 points    Problem Statement 10^9 contestants, numbered 1 to 10^9 , will compete in a competition.
There will be two contests in this competition.  The organizer prepared N problems, numbered 1 to N , to use in these contests.
When Problem i is presented in a contest, it will be solved by all contestants from Contestant L_i to Contestant R_i (inclusive), and will not be solved by any other contestants.  The organizer will use these N problems in the two contests.
Each problem must be used in exactly one of the contests, and each contest must have at least one problem.  The joyfulness of each contest is the number of contestants who will solve all the problems in the contest.
Find the maximum possible total joyfulness of the two contests.      Constraints  2 \leq N \leq 10^5  1 \leq L_i \leq R_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  L_1  R_1  L_2  R_2  \vdots  L_N  R_N       Output Print the maximum possible total joyfulness of the two contests.        Sample Input 1 4
4 7
1 4
5 8
2 5      Sample Output 1 6  The optimal choice is:   Use Problem 1 and 3 in the first contest. Contestant 5 , 6 , and 7 will solve both of them, so the joyfulness of this contest is 3 .  Use Problem 2 and 4 in the second contest. Contestant 2 , 3 , and 4 will solve both of them, so the joyfulness of this contest is 3 .  The total joyfulness of these two contests is 6 . We cannot make the total joyfulness greater than 6 .        Sample Input 2 4
1 20
2 19
3 18
4 17      Sample Output 2 34       Sample Input 3 10
457835016 996058008
456475528 529149798
455108441 512701454
455817105 523506955
457368248 814532746
455073228 459494089
456651538 774276744
457667152 974637457
457293701 800549465
456580262 636471526      Sample Output 3 540049931

Solution (Python):
import sys
input = sys.stdin.buffer.readline


class Segtree():
    def __init__(self, N):
        
        self.N0 = 2**(N-1).bit_length()
        self.INF = 2**31-1
        self.seg_min = [self.INF]*(2*self.N0)

    def update(self, index, value):
        index += self.N0 - 1
        self.seg_min[index] = value
        while index > 0:
            index = (index - 1) // 2
            self.seg_min[index] = min(self.seg_min[index * 2 + 1], self.seg_min[index * 2 + 2])

    def query(self, first, last):
        first += self.N0 - 1
        last += self.N0 - 1
        ret = self.INF
        while first <= last:
            if not first & 1:
                ret = min(ret, self.seg_min[first])
            if last & 1:
                ret = min(ret, self.seg_min[last])
            first = first // 2
            last = last // 2 - 1
        return ret


N = int(input())
prob = []
max_len = 0
max_len_pair = []
for _ in range(N):
    L, R = map(int, input().split())
    if max_len < R - L + 1:
        max_len = R - L + 1
        max_len_pair = [(L, R)]
    elif max_len == R - L + 1:
        max_len_pair.append((L, R))
    prob.append((L, R))
prob.sort(key=lambda x: x[1])
prob.sort(key=lambda x: x[0])

segtree_L = Segtree(N)
segtree_R = Segtree(N)
for i in range(N):
    segtree_L.update(i, -prob[i][0])
    segtree_R.update(i, prob[i][1])

ans_best = 0
for i in range(N-1):
    ans1 = max(segtree_R.query(0, i) + segtree_L.query(0, i) + 1, 0)
    ans2 = max(segtree_R.query(i+1, N-1) + segtree_L.query(i+1, N-1) + 1, 0)
    ans_best = max(ans_best, ans1+ans2)

max_len_pair.sort(key=lambda x: x[0])
ans_another1 = max_len
ans_another2 = max_len
flg = 0
for i in range(N):
    if prob[i] == max_len_pair[0]:
        idx = i
        flg += 1
    if prob[i] == max_len_pair[-1]:
        idx2 = i
        flg += 1
    if flg == 2:
        break

Lmax1 = 0
Rmin1 = 10**9+1
Lmax2 = 0
Rmin2 = 10**9+1
for i in range(N):
    if i != idx:
        Lmax1 = max(Lmax1, prob[i][0])
        Rmin1 = min(Rmin1, prob[i][1])
    if i != idx2:
        Lmax2 = max(Lmax2, prob[i][0])
        Rmin2 = min(Rmin2, prob[i][1])
ans_another1 += max(0, Rmin1 - Lmax1 + 1)
ans_another2 += max(0, Rmin2 - Lmax2 + 1)

print(max(ans_best, ans_another1, ans_another2))

Solution (Python):
import sys
sys.setrecursionlimit(10**9)
input = lambda: sys.stdin.readline().rstrip()
inpl = lambda: list(map(int,input().split()))
P = 10**9
N = int(input())
LR = [ inpl() for _ in range(N) ]
LR.sort()

K = 0
mlist = []
for i in range(N):
    l, r = LR[i]
    k = r -l + 1
    if k == K:
        mlist.append(i)
    elif k > K:
        mlist = [i]
        K = k
U = []
r = P
for i in range(N):
    l = LR[i][0]
    r = min(r, LR[i][1])
    U.append((l,r))
D = [None]*N
l = LR[-1][0]
for i in range(N):
    r = min(r, LR[N-1-i][1])
    D[N-1-i] = (l,r)

ans = K
for m in mlist:
    if m == 0:
        score = K + max(0, D[1][1]-D[1][0]+1)
    elif m == N-1:
        score = K + max(0, U[-2][1]-U[-2][0]+1)
    else:
        score = K + max(0, min(U[m-1][1],D[m+1][1]) - D[m+1][0] + 1)
    if score > ans:
        ans = score

LR2 = []
for i in range(N):
    while LR2 and LR2[-1][1] >= LR[i][1]:
        LR2.pop()
    LR2.append(LR[i])
M = len(LR2)
if M < 2:
    print(ans)
    exit()

R1 = LR2[0][1]
L2 = LR2[-1][0]
for i in range(M-1):
    L1 = LR2[i][0]
    R2 = LR2[i+1][1]
    score = max(0, R1-L1+1) + max(0, R2-L2+1)
    if score > ans:
        ans = score

print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
lr=[list(map(int,input().split())) for _ in range(n)]
lr.sort(key=lambda x:x[0])
lr.sort(key=lambda x:x[1])
mae=[]
l=0
r=10**9
for i in range(n-1):
    ll,rr=lr[i]
    l=max(ll,l)
    r=min(rr,r)
    mae.append(r-l+1)

usi=[]
l=0
r=10**9+1
for i in range(n-1,0,-1):
    ll,rr=lr[i]
    l=max(ll,l)
    r=min(rr,r)
    usi.append(r-l+1)
usi.reverse()

ans=0

for i in range(n-1):
    ans=max(mae[i]+usi[i],ans)

lr2=[(0,-1)]
ll=0
rr=10**9
for i in range(n-1):
    l,r=lr[i]
    ll=max(ll,l)
    rr=min(rr,r)
    lr2.append((ll,rr))
lr3=[(0,-1)]
ll=0
rr=10**9
for i in range(n-1,0,-1):
    l,r=lr[i]
    ll=max(ll,l)
    rr=min(rr,r)
    lr3.append((ll,rr))
lr3.reverse()

ans2=0
for i in range(n):
    l,r=lr[i]
    rr=min(lr2[i][1],lr3[i][1])
    ll=max(lr2[i][0],lr3[i][0])
    d=max(0,rr-ll+1)
    ans2=max(ans2,r-l+1+d)


ans=max(ans,ans2)



print(ans)

Solution (Python):
import itertools
import math
import os
import sys
from collections import defaultdict
from operator import itemgetter

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


class SparseTable:
    """
    構築 O(NlogN)、クエリ O(1)
    """

    def __init__(self, values, fn):
        """
        :param list values:
        :param callable fn: 結合則を満たす冪等な関数。min、max など。add はだめ
        """
        self._values = values
        self._fn = fn

        
        
        self._table = self._build(values, fn)

        
        self._msb = [0] * (len(values) + 1)
        for i in range(2, len(values) + 1):
            self._msb[i] = self._msb[i >> 1] + 1

    @staticmethod
    def _build(values, fn):
        
        size = int(math.log(len(values), 2)) + 1

        st = [[0] * size for _ in range(len(values))]
        for i in range(len(values)):
            st[i][0] = i
        for p in range(1, size):
            for i in range(len(values)):
                q = min(i + (1 << (p - 1)), len(values) - 1)
                l = st[i][p - 1]
                r = st[q][p - 1]
                if values[l] == fn(values[l], values[r]):
                    st[i][p] = l
                else:
                    st[i][p] = r
        return st

    def get(self, a, b):
        """
        半開区間 [a, b) に fn を適用した結果
        :param int a:
        :param int b:
        """
        if b <= a:
            return None
        p = self._msb[b - a]
        return self._fn(
            self._values[self._table[a][p]],
            self._values[self._table[b - (1 << p)][p]]
        )


N = int(sys.stdin.readline())
LR = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]


def calc_score(lr):
    ma = IINF
    mi = 0
    for l, r in lr:
        ma = min(ma, r)
        mi = max(mi, l)
    return max(0, ma - mi + 1)


def test(N, LR):
    import numpy as np
    LR = np.array(LR, dtype=int)
    ret = 0
    counts = defaultdict(int)
    for choice in itertools.product([True, False], repeat=N):
        if sum(choice) in [N, 0]:
            continue
        choice = np.array(choice)
        score = calc_score(LR[choice]) + calc_score(LR[~choice])
        if score >= ret:
            counts[score] = max(counts[score], sum(choice))
        ret = max(score, ret)
        
    
    return ret


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted([(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse)]


def solve():
    L, R = zip(*LR)
    L = list(L)
    R = list(R)
    if N == 2:
        ans = R[0] - L[0] + 1 + R[1] - L[1] + 1
        
        print(ans)
        exit()

    
    diff = [r - l for r, l in zip(R, L)]
    order = argsort(diff)
    L = [L[o] for o in order]
    R = [R[o] for o in order]
    diff.sort()
    li = L.index(max(L))
    ri = R.index(min(R))

    g1i = N - 1
    while g1i in [li, ri]:
        g1i -= 1
    g1 = diff[g1i] + 1
    g2 = max(0, R[ri] - L[li] + 1)
    ans1 = g1 + g2

    
    LR.sort()
    L, R = zip(*LR)
    rsp = SparseTable(R, min)
    ans2 = 0
    for sep in range(1, N):
        max_l = L[sep - 1]
        min_r = rsp.get(0, sep)
        s1 = max(0, min_r - max_l + 1)
        max_l = L[-1]
        min_r = rsp.get(sep, N)
        s2 = max(0, min_r - max_l + 1)
        score = s1 + s2
        ans2 = max(score, ans2)

    LR.sort(key=itemgetter(1))
    L, R = zip(*LR)
    lsp = SparseTable(L, max)
    for sep in range(1, N):
        max_l = lsp.get(0, sep)
        min_r = R[0]
        s1 = max(0, min_r - max_l + 1)
        max_l = lsp.get(sep, N)
        min_r = R[sep]
        s2 = max(0, min_r - max_l + 1)
        score = s1 + s2
        ans2 = max(score, ans2)

    return max(ans1, ans2)


print(solve())

Solution (Python):

import sys
sys.setrecursionlimit(10**8)


n = int(input())
lr = []
for i in range(n):
    l, r = [int(item) for item in input().split()]
    lr.append((l, r))
lr.sort()
al = lr[0][0]; ar = lr[0][1]; anum = ar - al + 1
bl = lr[1][0]; br = lr[1][1]; bnum = br - bl + 1



for i in range(2, n):
    nl = lr[i][0]; nr = lr[i][1]
    
    adda_l = max(al, nl)
    adda_r = min(ar, nr)
    adda_num = max(adda_r - adda_l + 1, 0)
    adda_ret = adda_num + bnum
    
    addb_l = max(bl, nl)
    addb_r = min(br, nr)
    addb_num = max(addb_r - addb_l + 1, 0)
    addb_ret = addb_num + anum
    
    create_l = max(al, bl)
    create_r = min(ar, br)
    create_num = max(create_r - create_l + 1, 0)
    cnum = nr - nl + 1
    create_ret = create_num + cnum

    if adda_ret >= addb_ret and adda_ret >= create_ret:
        al = adda_l
        ar = adda_r
        anum = adda_num
    elif addb_ret >= adda_ret and addb_ret >= create_ret:
        bl = addb_l
        br = addb_r
        bnum = addb_num
    else:
        al = create_l
        ar = create_r
        anum = create_num
        bl = nl
        br = nr
        bnum = cnum

print(anum + bnum)

Solution (Python):
import sys
input = sys.stdin.readline

N=int(input())
LR=[tuple(map(int,input().split())) for i in range(N)]

LR.sort()



seg_el=1<<(N.bit_length())
SEG=[1<<30]*(2*seg_el)

for i in range(N):
    SEG[i+seg_el]=LR[i][1]

for i in range(seg_el-1,0,-1):
    SEG[i]=min(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el):
    i=n+seg_el
    SEG[i]=x
    i>>=1
    
    while i!=0:
        SEG[i]=min(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):
    L=l+seg_el
    R=r+seg_el
    ANS=1<<30

    while L<R:
        if L & 1:
            ANS=min(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=min(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

SEG2=[-1]*(2*seg_el)

for i in range(N):
    SEG2[i+seg_el]=LR[i][0]

for i in range(seg_el-1,0,-1):
    SEG2[i]=max(SEG2[i*2],SEG2[i*2+1])

def update2(n,x,seg_el):
    i=n+seg_el
    SEG2[i]=x
    i>>=1
    
    while i!=0:
        SEG2[i]=max(SEG2[i*2],SEG2[i*2+1])
        i>>=1
        
def getvalues2(l,r):
    L=l+seg_el
    R=r+seg_el
    ANS=-1

    while L<R:
        if L & 1:
            ANS=max(ANS , SEG2[L])
            L+=1

        if R & 1:
            R-=1
            ANS=max(ANS , SEG2[R])
        L>>=1
        R>>=1

    return ANS

ANS=0

for i in range(N):
    ANS=max(ANS,LR[i][1]-LR[i][0]+1+max(0,min(getvalues(0,i),getvalues(i+1,N))-max(getvalues2(0,i),getvalues2(i+1,N))+1))

    

LR2=[LR[0]]

for i in range(N):
    if LR[i][0]==LR2[-1][0]:
        continue
    while len(LR2)>0 and LR2[-1][0]<=LR[i][0] and LR2[-1][1]>=LR[i][1]:
        LR2.pop()

    LR2.append(LR[i])

LN=len(LR2)

SEG=[1<<30]*(2*seg_el)

for i in range(LN):
    SEG[i+seg_el]=LR2[i][1]

for i in range(seg_el-1,0,-1):
    SEG[i]=min(SEG[i*2],SEG[i*2+1])

def update(n,x,seg_el):
    i=n+seg_el
    SEG[i]=x
    i>>=1
    
    while i!=0:
        SEG[i]=min(SEG[i*2],SEG[i*2+1])
        i>>=1
        
def getvalues(l,r):
    L=l+seg_el
    R=r+seg_el
    ANS=1<<30

    while L<R:
        if L & 1:
            ANS=min(ANS , SEG[L])
            L+=1

        if R & 1:
            R-=1
            ANS=min(ANS , SEG[R])
        L>>=1
        R>>=1

    return ANS

SEG2=[-1]*(2*seg_el)

for i in range(LN):
    SEG2[i+seg_el]=LR2[i][0]

for i in range(seg_el-1,0,-1):
    SEG2[i]=max(SEG2[i*2],SEG2[i*2+1])

def update2(n,x,seg_el):
    i=n+seg_el
    SEG2[i]=x
    i>>=1
    
    while i!=0:
        SEG2[i]=max(SEG2[i*2],SEG2[i*2+1])
        i>>=1
        
def getvalues2(l,r):
    L=l+seg_el
    R=r+seg_el
    ANS=-1

    while L<R:
        if L & 1:
            ANS=max(ANS , SEG2[L])
            L+=1

        if R & 1:
            R-=1
            ANS=max(ANS , SEG2[R])
        L>>=1
        R>>=1

    return ANS


for i in range(1,LN):
    ANS=max(ANS,max(0,getvalues(0,i)-getvalues2(0,i)+1)+max(0,getvalues(i,LN)-getvalues2(i,LN)+1))

    
    

print(ANS)

Solution (Python):
n=int(input())
lr=[[int(i) for i in input().split()] for j in range(n)]
lr=sorted(lr)
li_test=[]

for x,y in lr:
    li_test.append(y)

li=[li_test[0]]
a=li_test[0]
for i in range(1,n):
    a=min(li_test[i],a)
    li.append(a)

li_test=li_test[::-1]
li2=[li_test[0]]
a=li_test[0]
for i in range(1,n):
    a=min(li_test[i],a)
    li2.append(a)
li2=li2[::-1]
    
ans=0


maxi=lr[-1][0]
for i in range(n-1):
    one = max(0,li[i]-lr[i][0]+1)
    two = max(0,li2[i+1]-maxi+1)
    tokubetu=lr[i][1]-lr[i][0]+1
    tokubetu2=max(0,li2[0]-maxi+1)
    check=max(one+two,tokubetu+tokubetu2)
    ans=max(ans,check)
print(ans)

Solution (Python):



import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

n = int(input())
lr = [[int(i) for i in readline().split()] for _ in range(n)]

from operator import itemgetter
lr.sort(key=itemgetter(1),reverse=True)

a,b = lr.pop()
lr.sort(reverse=True) 

if n == 2:
    c,d=lr[0]
    print(d-c+1+b-a+1)
    exit()



res = 0
for l,r in lr[1:]:
    res = max(res,r-l+1)

ans = res + max(0,b-max(a,lr[0][0])+1)


c,d = lr[0]
for l,r in lr[1:]:
    res = max(d-c+1,0) + max(b-l+1,0)
    ans = max(ans,res)
    c = max(c,l)
    d = min(d,r)



c = 0
d = 10**9
for l,r in lr:
    c = max(c,l)
    d = min(d,r)
ans = max(ans,max(d-c+1,0)+b-a+1)


print(ans)

Solution (Python):
n=int(input())
it=[]
for _ in range(n):
    it.append(list(map(int,input().split())))
it.sort()
ac=[i+[j] for j,i in enumerate(it[:])]
ac.sort(key=lambda x:x[1])
bc=[i+[j] for j,i in enumerate(it[:])]
bc.sort(key=lambda x:x[0],reverse=True)

maa=0
mi=bc[0][0]
ma=ac[0][1]
a=0
b=0
for i in range(n):
    if i==ac[0][2]:
        ma=ac[1][1]
        a=1
    if i==bc[0][2]:
        mi=bc[1][0]
        b=1
   
    maa=max(max(ma-mi+1,0)+it[i][1]-it[i][0]+1,maa)
    if a:
        ma=ac[0][1]
        a=0
    if b:
        mi=bc[0][0]
        b=0

aa=[0]*n
bb=[0]*n
aa[0]=it[0][1]-it[0][0]+1
mi=it[0][0]
ma=it[0][1]
for i in range(1,n-1):
    mi=max(mi,it[i][0])
    ma=min(ma,it[i][1])
    so=ma-mi+1
    if so<0:
        so=0
    aa[i]=so

bb[-1]=it[-1][1]-it[-1][0]+1
mi=it[-1][0]
ma=it[-1][1]

for i in range(n-2,0,-1):
    mi=max(mi,it[i][0])
    ma=min(ma,it[i][1])
    so=ma-mi+1
    if so<0:
        so=0
    bb[i]=so
ma=aa[0]+bb[1]
for i in range(1,n-1):
    ma=max(ma,aa[i]+bb[i+1])
print(max(ma,maa))

Solution (Python):
n = int(input())
problem = [list(map(int, input().split())) for _ in range(n)]

problem.sort()

min_r_up = [0] * n
r = problem[0][1]
for i in range(n):
    r = min(r, problem[i][1])
    min_r_up[i] = r

min_r_down = [0] * n
r = problem[-1][1]
for i in reversed(range(n)):
    r = min(r, problem[i][1])
    min_r_down[i] = r


ans = 0

for i in range(n-1):
    num = 0
    l1 = problem[i][0]
    l2 = problem[-1][0]

    
    r1 = problem[i][1]
    if i >= 1:
        if min_r_up[i-1] < r1:
            r2 = min(min_r_up[i-1], min_r_down[i+1])
        else:
            r2 = min_r_down[i+1]
    else:
        r2 = min_r_down[i+1]

    num += max(0, r1-l1+1)
    num += max(0, r2-l2+1)

    ans = max(ans, num)

    
    r1 = min_r_up[i]
    r2 = min_r_down[i+1]

    num = 0
    num += max(0, r1-l1+1)
    num += max(0, r2-l2+1)
    ans = max(ans, num)


print(ans)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, LR):
    LR.sort(key=lambda x: x[1])
    LR.sort(key=lambda x: x[0])


    lc = []
    l = 0
    r = INF
    for i in range(N):
        l_, r_ = LR[i]
        l = max(l, l_)
        r = min(r, r_)
        lc.append((l, r))
    
    rc = []
    l = 0
    r = INF
    for i in range(N-1, -1, -1):
        l_, r_ = LR[i]
        l = max(l, l_)
        r = min(r, r_)
        rc.append((l, r))
    
    def c(l, r):
        return max(0, r-l+1)

    ans = 0
    for i in range(N-1):
        ans = max(ans, c(*lc[i]) + c(*rc[N-1-1-i]))
    for i in range(N):
        tmp = c(*LR[i])
        l, r = (0, INF)
        if i != 0:
            l = max(l, lc[i-1][0])
            r = min(r, lc[i-1][1])
        if i != N-1:
            l = max(l, rc[N-1-i][0])
            r = min(r, rc[N-1-i][1])
            
        tmp += c(l, r)
        ans = max(ans, tmp)

    return ans


def main():
    N = read_int()
    LR = [read_int_n() for _ in range(N)]
    print(slv(N, LR))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline

def solve():
    N = int(input())
    LRs = []
    Ls, Rs = [], []
    for _ in range(N):
        L, R = map(int, input().split())
        LRs.append((L, R))
        Ls.append(L)
        Rs.append(R)

    Ls.sort(reverse=True)
    Rs.sort()

    maxL, maxL2 = Ls[:2]
    minR, minR2 = Rs[:2]

    
    ans = 0
    for L, R in LRs:
        num = R-L+1
        A, B = maxL, minR
        if L == maxL:
            A = maxL2
        if R == minR:
            B = minR2
        num += max(0, B-A+1)
        ans = max(ans, num)

    
    LRs.sort(key=lambda x: x[0])

    minR = LRs[0][1]
    accMinRs = [minR]
    for L, R in LRs[1:]:
        minR = min(minR, R)
        accMinRs.append(minR)
    minR = LRs[-1][1]
    accMinRRevs = [minR]
    for L, R in reversed(LRs[:-1]):
        minR = min(minR, R)
        accMinRRevs.append(minR)
    accMinRRevs = accMinRRevs[::-1]

    for i in range(N-1):
        num = max(0, accMinRs[i] - LRs[i][0] + 1)
        num += max(0, accMinRRevs[i+1] - LRs[-1][0] + 1)
        ans = max(ans, num)

    
    LRs.sort(key=lambda x: x[1])

    maxL = LRs[0][0]
    accMaxLs = [maxL]
    for L, R in LRs[1:]:
        maxL = max(maxL, L)
        accMaxLs.append(maxL)
    maxL = LRs[-1][0]
    accMaxLRevs = [maxL]
    for L, R in reversed(LRs[:-1]):
        maxL = max(maxL, L)
        accMaxLRevs.append(maxL)
    accMaxLRevs = accMaxLRevs[::-1]

    for i in range(N-1):
        num = max(0, LRs[0][1] - accMaxLs[i] + 1)
        num += max(0, LRs[i+1][1] - accMaxLRevs[i+1] + 1)
        ans = max(ans, num)

    print(ans)


solve()

Solution (Python):
from operator import itemgetter
n=int(input())
l=[list(map(int,input().split())) for i in range(n)]
for i in range(n):
  l[i]=[l[i][0],l[i][1],(l[i][0]+l[i][1])/2]
len=[]
for i in range(n):
  len.append(l[i][1]-l[i][0]+1)
maxlen=max(len)
x=len.index(maxlen)
L3=1;R3=10**9
for i in range(n):
  if l!=x:
    L3=max(L3,l[i][0])
    R3=min(R3,l[i][1])
c=maxlen+max(R3-L3+1,0)

l=sorted(l,key=itemgetter(2))
L=[]
R=[]
for i in range(n):
  L.append(l[i][0])
for i in range(n):
  R.append(l[i][1])
L1=1;R1=10**9
L2=1;R2=10**9
list=[]
list2=[]
for i in range(n-1):
  L1=max(L1,l[i][0])
  R1=min(R1,l[i][1])
  list.append(max(R1-L1+1,0))
for i in range(n-1,0,-1):
  L2=max(L2,l[i][0])
  R2=min(R2,l[i][1])
  list2.append(max(R2-L2+1,0))

list2.reverse()
ans=[]
for i in range(n-1):
  ans.append(list[i]+list2[i])
a=max(ans)
print(max(a,c))

Solution (Python):
import sys
from itertools import accumulate


def calc(tasks):
    tasks_l, tasks_r = zip(*tasks)
    tasks_l_acc_fwd = list(accumulate(tasks_l, func=max))
    tasks_l_acc_bwd = list(reversed(list(accumulate(reversed(tasks_l), func=max))))
    tasks_r_acc_fwd = list(accumulate(tasks_r, func=min))
    tasks_r_acc_bwd = list(reversed(list(accumulate(reversed(tasks_r), func=min))))
    
    
    

    score = 0
    for i in range(1, n):
        left_max_l = tasks_l_acc_fwd[i - 1]
        left_min_r = tasks_r_acc_fwd[i - 1]
        right_max_l = tasks_l_acc_bwd[i]
        right_min_r = tasks_r_acc_bwd[i]
        tmp_score = max(0, left_min_r - left_max_l + 1) + max(0, right_min_r - right_max_l + 1)
        score = max(score, tmp_score)
    return score


n = int(input())
appeared_lr = set()
tasks = []
for line in sys.stdin:
    l, r = list(map(int, line.split()))
    appeared_lr.add(l)
    appeared_lr.add(r)
    tasks.append((l, r))

tasks.sort()
ans1 = calc(tasks)

tasks.sort(key=lambda lr: (lr[0], -lr[1]))
ans2 = calc(tasks)

tasks.sort(key=lambda lr: (lr[1] - lr[0], lr[0], lr[1]))
ans3 = calc(tasks)

print(max(ans1, ans2, ans3))

Solution (Python):

def sc(l,r):
    return max(0,r-l+1)

N = int(input())

al1 = 0
al2 = 0
ar1 = 0
ar2 = 0
nmax = 0

LR = []
for i in range(N):
    nL,nR = map(int,input().split())
    LR.append([nL,nR])

LR.sort()

for i in range(N):

    L = LR[i][0]
    R = LR[i][1]

    if i == 0:
        al1 = L
        ar1 = R

    elif i == 1:
        al2 = L
        ar2 = R

    else:

        nmax = 0
        nmax = max(nmax, sc(max(al1,al2),min(ar1,ar2)) + sc(L,R) )
        nmax = max(nmax, sc(max(al1,L),min(ar1,R)) + sc(al2,ar2) )
        nmax = max(nmax, sc(max(al2,L),min(ar2,R)) + sc(al1,ar1) )
        

        if nmax == (sc(max(al1,al2),min(ar1,ar2)) + sc(L,R)):

            nal1 = max(al1,al2)
            nar1 = min(ar1,ar2)
            nal2 = L
            nar2 = R
            

        elif nmax == (sc(max(al1,L),min(ar1,R)) + sc(al2,ar2) ):

            nal1 = max(al1,L)
            nar1 = min(ar1,R)
            nal2 = al2
            nar2 = ar2
            

        else:

            nal1 = max(al2,L)
            nar1 = min(ar2,R)
            nal2 = al1
            nar2 = ar1
            

        al1 = nal1
        al2 = nal2
        ar1 = nar1
        ar2 = nar2

    

print (sc(al1,ar1) + sc(al2,ar2))

Solution (Python):
N = int(input())
LR = [list(map(int, input().split())) for _ in range(N)]

def honya(LR):
  l = LR[-1][0]
  r = LR[-1][1]
  D = [0] * N
  for i in range(N - 1, -1, -1):
    l = max(l, LR[i][0])
    r = min(r, LR[i][1])
    D[i] = max(0, r - l + 1)

  l = LR[0][0]
  r = LR[0][1]
  ans = 0
  for i in range(N - 1):
    r = min(r, LR[i][1])
    ans = max(ans, max(r - l + 1, 0) + D[i + 1])

  return ans

LR.sort(reverse = True)


  
ans = honya(LR)

R = 0
for i in range(N):
  R = max(R, LR[i][1])
for i in range(N):
  LR[i][0], LR[i][1] = R - LR[i][1], R - LR[i][0]
  
LR.sort(reverse = True)
ans = max(ans, honya(LR))

def honyamorake(LR):
  ans = 0
  x = 0
  for i in range(N):
    t = LR[i][1] - LR[i][0] + 1
    if t > ans:
      ans = t
      x = i
  return ans + honyapun(LR, x)

def honyapun(LR, x):
  l = 0
  r = 10 ** 10
  for i in range(N):
    if i != x:
      l = max(l, LR[i][0])
      r = min(r, LR[i][1])
  if l > r:
    return 0
  else:
    return r - l + 1

ans = max(ans, honyamorake(LR))

print(ans)

Solution (Python):
n=int(input())
data=[list(map(int,input().split())) for i in range(n)]
data.sort()
l,r=data[0]
lst=[0]*n
lst[0]=r-l+1
for i in range(1,n):
    a,b=data[i]
    l=a
    if b<r:
        r=b
    lst[i]=max(0,r-l+1)
li=[0]*n
l,r=data[n-1]
li[n-1]=r-l+1
for i in range(1,n):
    a,b=data[n-1-i]
    if b<r:
        r=b
    li[n-1-i]=max(0,r-l+1)
k=0
s=0
for i in range(n):
    l,r=data[i]
    if k<=r-l+1:
        k=r-l+1
        s=i
l=0
r=10**9+1
for i in range(n):
    if i==s:
        continue
    a,b=data[i]
    l=max(l,a)
    r=min(r,b)
ans=k+max(0,r-l+1)
for i in range(n-1):
    ans=max(ans,lst[i]+li[i+1])
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

task = []
N = int(input())
for _ in range(N):
    task.append(list(map(int, input().split())))

task.sort()

ans = 0

task_minmax = [None] * (N+1)
task_minmax[N] = [0, 10**9]
for i in range(N-1, -1, -1):
    task_minmax[i] = [max(task_minmax[i+1][0], task[i][0]), min(task_minmax[i+1][1], task[i][1])]

mini = 0
maxi = 10**9



for i in range(N-1):
    temp = 0
    if i != 0:
        ans = max(ans, max(0, min(maxi, task_minmax[i+1][1]) - max(mini, task_minmax[i+1][0]) + 1) + (task[i][1] - task[i][0]) + 1)

    mini = max(task[i][0], mini)
    maxi = min(task[i][1], maxi)

    temp += max(maxi - mini + 1, 0)
    temp += max(task_minmax[i+1][1] - task_minmax[i+1][0] + 1, 0)

    ans = max(temp, ans)

print(ans)

Solution (Python):
from operator import itemgetter
import bisect


def cross(a, b):
    l = max(a[0], b[0])
    r = min(a[1], b[1])
    if l <= r:
        return (l, r)
    else:
        return (-1, -2)
    
n = int(input())
info = [list(map(int, input().split())) for i in range(n)]
info = sorted(info, key = itemgetter(1))
max_ans = 0

l_ans = [(0, 10**9)]
for i in range(n):
    tmp = cross(l_ans[-1], info[i])
    l_ans.append(tmp)

r_ans = [(0, 10**9)]
for i in range(n)[::-1]:
    tmp = cross(r_ans[-1], info[i])
    r_ans.append(tmp)
r_ans = r_ans[::-1]

for i in range(1,n):
    ans = (l_ans[i][1] - l_ans[i][0]) + (r_ans[i][1] - r_ans[i][0]) + 2
    max_ans = max(ans, max_ans)
    
for i in range(n):
    ans = info[i][1] - info[i][0] + 1
    tmp = cross(l_ans[i], r_ans[i+1])
    ans += tmp[1] - tmp[0] + 1
    max_ans = max(ans, max_ans)

info = sorted(info)
l_ans = [(0, 10**9)]
for i in range(n):
    tmp = cross(l_ans[-1], info[i])
    l_ans.append(tmp)

r_ans = [(0, 10**9)]
for i in range(n)[::-1]:
    tmp = cross(r_ans[-1], info[i])
    r_ans.append(tmp)
r_ans = r_ans[::-1]

for i in range(1,n):
    ans = (l_ans[i][1] - l_ans[i][0]) + (r_ans[i][1] - r_ans[i][0]) + 2
    max_ans = max(ans, max_ans)
print(max_ans)

Solution (Python):
from heapq import heappop, heappush


def solve_b(n, l_list, r_list):

    l_max = max(l_list)
    r_min = min(r_list)

    
    res_1 = max(0, r_min - l_max + 1)
    
    res_1 += max([r_list[i] - l_list[i] + 1 for i in range(n)])

    
    hr = []
    for i in range(n):
        if r_list[i] > r_min:
            heappush(hr, (r_list[i], i))
    r_need = min([r_list[i] for i in range(n) if l_list[i] == l_max])
    l_temp = max([l_list[i] for i in range(n) if r_list[i] == r_min])

    res_2 = 0
    while len(hr) > 0:
        r, i = heappop(hr)
        res_2 = max(res_2, max(0, min(r, r_need) - l_max + 1) + max(0, r_min - l_temp + 1))
        l_temp = max(l_temp, l_list[i])
    res_2 = max(res_2, max(0, r_need - l_max + 1) + max(0, r_min - l_temp + 1))

    return max(res_1, res_2)


def main():
    n = int(input())
    l_list = [0] * n
    r_list = [0] * n
    for i in range(n):
        l, r = map(int, input().split())
        l_list[i] = l
        r_list[i] = r
    res = solve_b(n, l_list, r_list)
    print(res)


def test():
    assert solve_b(4, [4, 1, 5, 2], [7, 4, 8, 5]) == 6
    assert solve_b(4, [1, 2, 3, 4], [20, 19, 18, 17]) == 34


if __name__ == "__main__":
    test()
    main()