Problem: There are N integers X_1, X_2, \cdots, X_N, and we know that A_i \leq X_i \leq B_i. Find the number of different values that the median of X_1, X_2, \cdots, X_N can take.

Submission attempts (in order):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans


n = onem()

le = []

ri = []

if n % 2 != 0:
	for i in range(n):
		a,b = m()
		le.append(a)
		ri.append(b)
	le.sort()
	ri.sort()
	print(ri[n//2+1] - le[n//2+1]+1)



else:
	for i in range(n):
		a,b = m()
		le.append(a*2)
		ri.append(b*2)
	le.sort()
	ri.sort()
	print(ri[n//2] - le[n//2-1]+1)




import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans


n = onem()

le = []

ri = []

if n % 2 != 0:
	for i in range(n):
		a,b = m()
		le.append(a)
		ri.append(b)
	le.sort()
	ri.sort()
	print(ri[n//2] - le[n//2]+1)



else:
	for i in range(n):
		a,b = m()
		le.append(a*2)
		ri.append(b*2)
	le.sort()
	ri.sort()
	print(((ri[n//2]) - le[n//2-1]+1)//2)




import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans


n = onem()

le = []

ri = []

if n % 2 != 0:
	for i in range(n):
		a,b = m()
		le.append(a)
		ri.append(b)
	le.sort()
	ri.sort()
	print(ri[n//2] - le[n//2]+1)



else:
	for i in range(n):
		a,b = m()
		le.append(a*2)
		ri.append(b*2)
	le.sort()
	ri.sort()
	print(((ri[n//2]+ri[n//2-1]) - (le[n//2]+le[n//2-1]))//2+1)




Verdicts: Wrong Answer

Wrong Answer

Accepted