Problem:
 Score : 500 points    Problem Statement 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.      Notes The median of X_1, X_2, \cdots, X_N is defined as follows. Let x_1, x_2, \cdots, x_N be the result of sorting X_1, X_2, \cdots, X_N in ascending order.   If N is odd, the median is x_{(N+1)/2} ;  if N is even, the median is (x_{N/2} + x_{N/2+1}) / 2 .       Constraints  2 \leq N \leq 2 \times 10^5  1 \leq A_i \leq B_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  A_1  B_1  A_2  B_2  :  A_N  B_N       Output Print the answer.        Sample Input 1 2
1 2
2 3      Sample Output 1 3    If X_1 = 1 and X_2 = 2 , the median is \frac{3}{2} ;    if X_1 = 1 and X_2 = 3 , the median is 2 ;    if X_1 = 2 and X_2 = 2 , the median is 2 ;    if X_1 = 2 and X_2 = 3 , the median is \frac{5}{2} .    Thus, the median can take three values: \frac{3}{2} , 2 , and \frac{5}{2} .       Sample Input 2 3
100 100
10 10000
1 1000000000      Sample Output 2 9991

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from bisect import bisect_left, bisect_right
n = int(input())
a = [None] * n
b = [None] * n
for i in range(n):
    a[i], b[i] = map(int, input().split())
    
a.sort()
b.sort()
thre = n//2 if n%2 else n//2-1
def sub(x):
    
    small = bisect_right(a, x) - 1
    large = n - bisect_left(b, x) - 1
    if small>=thre and large>=thre:
        return True
    else:
        return False
    
l = 0
r = 10**9+1

def mid(l):
    if n%2:
        return l[n//2]
    else:
        return (l[n//2-1]+l[n//2])/2
    
ml = mid(a)
mr = mid(b)

if n%2:
    print(mr - ml + 1)
else:
    print(int(2*mr - 2*ml + 1))

Solution (Python):
N = int(input())
A = []
B = []
for _ in range(N):
  a,b = list(map(int, input().split()))
  A.append(a)
  B.append(b)

A.sort()
B.sort()

if N%2 != 0:
  print(B[(N+1)//2-1]-A[(N+1)//2-1]+1)
else:
  print(int((((B[(N)//2-1]+B[(N)//2])/2)-((A[(N)//2-1]+A[(N)//2])/2))*2+1))

Solution (Python):
N = int(input())

MIN = []
MAX = []
for i in range(N):
  a,b = map(int,input().split())
  MIN.append(a)
  MAX.append(b)

MIN.sort()
MAX.sort()

if N%2 == 1:
  C = (N+1)//2-1 
  ans = MAX[C]-MIN[C]+1
else:
  C = N//2-1
  D = C+1
  small = (MIN[C]+MIN[D])/2
  big = (MAX[C]+MAX[D])/2
  
  ans = (big-small)/0.5+1
  ans = int(ans)
print(ans)

Solution (Python):
from statistics import median
N = int(input())
A, B = zip(*tuple(tuple(map(int, input().split())) for _ in range(N)))
if N & 1:
    print(median(B) - median(A) + 1)
else:
    print(int((median(B) - median(A)) * 2 + 0.1) + 1)

Solution (Python):

N = int(input())
AB = [list(map(int,input().split())) for _ in [0]*N]

c = [0]*N
d = [0]*N
for i,ab in enumerate(AB):
    a,b = ab
    c[i] = a
    d[i] = b
c.sort()
d.sort(reverse=True)

if N%2:
    L = c[N//2]
    R = d[N//2]
    print(R-L+1)
else:
    L1 = c[N//2-1]
    R1 = d[N//2]
    L2 = c[N//2]
    R2 = d[N//2-1]
    print((R1+R2)-(L1+L2)+1)

Solution (Python):
n = int(input())
a, b = [], []
for _ in range(n):
    i, j = map(int, input().split())
    a.append(i)
    b.append(j)

a.sort()
b.sort()

if n % 2 == 1:
    mi = a[n // 2]
    ma = b[n // 2]
    print(ma - mi + 1)
    exit()

mi = a[n // 2 - 1] + a[n // 2]
ma = b[n // 2 - 1] + b[n // 2]
print(ma - mi + 1)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))


n = readint()
ab = [readints() for i in range(n)]


if n%2==1:
    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if a<=m:
                x+=1
        if x>=n//2+1:
            r = m
        else:
            l = m
    left = r
    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if m<=b:
                x+=1
        if x>=n//2+1:
            l = m
        else:
            r = m
    right = l
    print(right-left+1)
else:
    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if a<=m:
                x+=1
        if x>=n//2:
            r = m
        else:
            l = m
    left1 = r

    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if a<=m:
                x+=1
        if x>=n//2+1:
            r = m
        else:
            l = m
    left2 = r

    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if m<=b:
                x+=1
        if x>=n//2:
            l = m
        else:
            r = m
    right1 = l

    l = -1
    r = 10**9+1
    while l+1 != r:
        m = (l+r)//2
        x = 0
        for i in range(n):
            a,b = ab[i]
            if m<=b:
                x+=1
        if x>=n//2+1:
            l = m
        else:
            r = m
    right2 = l
    ans = 0
    ans += right2+right1 - left2-left1 + 1
    print(ans)

Solution (Python):
N = int(input())
A = [0] *N
B = [0]*N
for i in range(N):
    a, b = map(int,input().split())
    A[i] = a
    B[i] = b
A = sorted(A)
B = sorted(B)
if N %2 ==1:
    M = (N+1)//2
    left = A[M-1]
    right = B[-M]
    ans = right - left +1
else:
    M1 = N//2
    M2 = M1+1
    left1 = A[M1-1]
    right1 =B[-M1]
    left2 = A[M2-1]
    right2  =B[-M2]
    ans = right2 + right1 -left1-left2+1
print(ans)

Solution (Python):
N=int(input())
A=[]
B=[]
for i in range(N):
  a,b=map(int,input().split())
  A.append(a)
  B.append(b)
A=sorted(A)
B=sorted(B)
if N%2==0:
  m=A[N//2]+A[N//2-1]
  M=B[N//2]+B[N//2-1]
  print(M-m+1)
else:
  m=A[N//2]
  M=B[N//2]
  print(M-m+1)

Solution (Python):
N = int(input())
A = [0]*N
B = [0]*N 
for i in range(N):
    s,t = map(int,input().split())
    A[i] = s
    B[i] = t
A.sort()
B.sort()
if N%2 == 1:
    a = A[(N-1)//2]
    b = B[(N-1)//2]
    print(b-a+1)
if N%2 == 0:
    a = A[N//2 - 1] + A[N//2]
    b = B[N//2 - 1] + B[N//2]
    print(b-a+1)

Solution (Python):
import statistics

N = int(input())
a = []
b = []
for i in range(N):
    A,B = map(int, input().split())
    a.append(A)
    b.append(B)

a2 = statistics.median(a)
b2 = statistics.median(b)

if N % 2 == 0:
    c = (b2-a2)/0.5 + 1
    print(int(c))
else:
    print(b2-a2+1)

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
n = int(readline())
import numpy as np
kx = np.array(read().split(),np.int32)
a = kx[::2]
b = kx[1::2]
a.sort()
b.sort()
if n%2 == 1:
  L = a[n//2]
  R = b[n//2]
  ans = R-L+1
else:
  LL = a[n//2-1]
  LR = b[n//2-1]
  RL = a[n//2]
  RR = b[n//2]
  ans = RR+LR-LL-RL+1
print(ans)

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

N = int(input())
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = map(int, input().split())
    if N % 2 == 0:
        A[i] *= 2
        B[i] *= 2
A.sort()
B.sort()
if N % 2 == 1:
    print(B[N//2] - A[N//2] + 1)
else:
    print((B[N//2-1] + B[N//2] - A[N//2-1] - A[N//2]) // 2 + 1)

Solution (Python):
n = int(input())
a = []
b = []
for i in range(n):
  x,y = map(int,input().split())
  a.append(x)
  b.append(y)
a.sort()
b.sort()
if n % 2 == 1:
  print(b[n//2] - a[n//2] + 1)
else:
  print(b[n//2]+b[n//2-1]-a[n//2]-a[n//2-1]+1)

Solution (Python):
N = int(input())
A = []
B = []
for i in range(N):
  Anew, Bnew = map(int,input().split())
  A.append(Anew)
  B.append(Bnew)
A.sort()
B.sort()
if N % 2 == 0:
  min = (A[N//2-1] + A[N//2]) / 2
  max = (B[N//2-1] + B[N//2]) / 2
  print(int((max-min)*2+1))
else:
  min = (A[(N-1)//2])
  max = (B[(N-1)//2])
  print(max-min+1)

Solution (Python):

import statistics


N = int(input())



A = []
B = []
for i in range(N):
    a, b = map(int,input().split())
    A.append(a)
    B.append(b)








if(N%2 == 1):
    lowest = statistics.median(A)
    highest = statistics.median(B)
    ans = highest - lowest + 1
else:
    lowest = statistics.median(A)
    highest = statistics.median(B)
    ans = (2 * highest) - (2 * lowest) + 1

print(int(ans))

Solution (Python):
n=int(input())
ar=[list(map(int,input().split())) for i in range(n)]
low=[ar[i][0] for i in range(n)]
high=[ar[i][1] for i in range(n)]
low.sort()
high.sort()
if n%2==1:
    print(high[n//2]-low[n//2]+1)
else:
    l=(low[n//2]+low[n//2-1])/2
    h=(high[n//2]+high[n//2-1])/2
    print(int((h-l)*2)+1)

Solution (Python):
n=int(input())
l1=[]
l2=[]
for i in range(n):
    a,b=map(int,input().split())
    l1.append(a)
    l2.append(b)
l1.sort()
l2.sort()
if n%2==0:
    low=l1[n//2]+l1[n//2-1]
    high=l2[n//2]+l2[n//2-1]
    print(high-low+1)
else:
    low=l1[n//2]
    high=l2[n//2]
    print(high-low+1)

Solution (Python):
N=int(input())

A=[]
B=[]
for k in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()
    
if N%2==1:
    mA=A[(N-1)//2]
    mB=B[(N-1)//2]
    print(mB-mA+1)
else:
    nA=A[N//2]+A[N//2-1]
    nB=B[N//2]+B[N//2-1]
    print(nB-nA+1)

Solution (Python):
N = int(input())
import numpy as np
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = map(int,input().split())
na = np.median(A)
nb = np.median(B)
if N%2 == 1:
    ans = int(nb - na + 1)
    print(ans)
    exit()
else:
    ans = int(2*(nb - na)) + 1
    print(ans)
    exit()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
A=[0]*N
B=[0]*N
for i in range(N):
    a,b=map(int,input().split())
    A[i]=a
    B[i]=b
A.sort()
B.sort()
if N%2:
    print(B[N//2]-A[N//2]+1)
else:
    a=A[N//2-1]+A[N//2]
    b=B[N//2-1]+B[N//2]
    print(b-a+1)

Solution (Python):
import statistics

n = int(input())
a = []
b = []

for i in range(n):
  _a, _b = map(int, input().split())
  a.append(_a)
  b.append(_b)

max_median = statistics.median(b)
min_median = statistics.median(a)
if n % 2 == 0:
  print(int((max_median - min_median) * 2) + 1)
else:
  print(int(max_median - min_median) + 1)

Solution (Python):
import math

n = int(input())
ab = [list(map(int,input().split())) for _ in range(n)]

al = []
bl = []
for a,b in ab:
  al.append(a)
  bl.append(b)
al.sort()
bl.sort()

if n%2==0:
  mn = (al[n//2-1]+al[n//2])/2
  mx = (bl[n//2-1]+bl[n//2])/2
  ans = math.floor((mx-mn)*2+1)
else:
  mn = al[n//2]
  mx = bl[n//2]
  ans = mx-mn+1

print(ans)

Solution (Python):
n = int(input())
A = []
B = []

for _ in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()

if n % 2 == 0:
    minimum = (A[n//2 - 1] + A[n//2]) // 2
    mini_minus = (A[n//2 - 1] + A[n//2]) % 2
    maximum = (B[n//2 - 1] + B[n//2]) // 2
    maxim_add = (B[n//2 - 1] + B[n//2]) % 2

    ans = (maximum - minimum) * 2 + 1 - mini_minus + maxim_add

else:
    minimum = A[n//2]
    maximum = B[n//2]
    ans = maximum - minimum + 1

print(ans)

Solution (Python):
import statistics

n = int(input())
A = []
B = []
for i in range(n):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A.sort()
B.sort()
am = statistics.median(A)
bm = statistics.median(B)

if n % 2 == 0:
    print(int(bm * 2 - am * 2 + 1))
else:
    print(int(bm - am + 1))

Solution (Python):
N=int(input())

min_x=[]
max_x=[]
for _ in range(N):
    A,B=map(int,input().split())
    min_x.append(A)
    max_x.append(B)

min_x.sort()
max_x.sort()

if N%2==0:
    center=N//2
    min_tmp=(min_x[center]+min_x[center-1])
    max_tmp=(max_x[center]+max_x[center-1])
    print(max_tmp-min_tmp+1)
else:
    center=N//2
    print(max_x[center]-min_x[center]+1)

Solution (Python):
n = int(input())
a = []
b = []
for i in range(n):
   ai,bi = [int(j) for j in input().split()]
   a.append(ai)
   b.append(bi)
a.sort()
b.sort()
if n == 1:
   ans = b[0] - a[0] + 1
elif n % 2 == 1:
   tg = (n+1) // 2
   ans = b[-tg] - a[tg-1] + 1
else:
   tg = n//2
   ans = b[-tg] + b[-tg-1] - a[tg-1] - a[tg] +1
print(ans)

Solution (Python):
import sys
from collections import Counter
from collections import deque
import heapq
import math
import fractions
import bisect
import itertools
import statistics
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n=int(input())
l=[lmp() for i in range(n)]
a=[0]*n
b=[0]*n
for i in range(n):
    a[i]=l[i][0]
    b[i]=l[i][1]
ma=statistics.median(a)
mb=statistics.median(b)
if n%2==0:
    print(int((mb-ma)*2+1))
else:
    print(int((mb-ma)+1))

Solution (Python):
n = int(input())
A = []
B = []
for _ in range(n):
    a,b = map(int,input().split())
    A += [a]
    B += [b]
A.sort()
B.sort()
if n % 2 == 1:
    print(B[n//2]-A[n//2]+1)
else:
    a1 = A[n//2-1]
    a2 = A[n//2]
    b1 = B[n//2-1]
    b2 = B[n//2]
    print(b2+b1-a2-a1+1)

Solution (Python):

import sys
import math
from bisect import bisect_left, bisect_right, insort_left, insort_right
from collections import defaultdict, deque, Counter
from copy import deepcopy
from fractions import gcd
from functools import lru_cache, reduce
from heapq import heappop, heappush
from itertools import accumulate, groupby, product, permutations, combinations, combinations_with_replacement
from math import ceil, floor, factorial, log, sqrt, sin, cos
from operator import itemgetter
from string import ascii_lowercase, ascii_uppercase, digits
sys.setrecursionlimit(10**6)
INF = float('inf')
MOD = 10 ** 9 + 7
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(rs())
def rf(): return float(rs())
def rs_(): return [_ for _ in rs().split()]
def ri_(): return [int(_) for _ in rs().split()]
def rf_(): return [float(_) for _ in rs().split()]
def divisors(n, sortedresult=True):
    div = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            div.append(i)
            if i != n // i:
                div.append(n//i)
    if sortedresult:
        div.sort()
    return div


N = ri()
A = [0] * N
B = [0] * N
for i in range(N):
    A[i], B[i] = ri_()
A.sort()
B.sort()
if N % 2 == 1:
    ans = B[(N - 1) // 2] - A[(N - 1) // 2] + 1
else:
    ans = (B[N // 2 - 1] + B[N // 2]) - (A[N // 2 - 1] + A[N // 2]) + 1
print(ans)

Solution (Python):
N = int(input())
list = [list(map(int,input().split())) for i in range(N)]
if N%2 == 1:
  list.sort()
  
  m = list[(N+1)//2-1][0]
  
  list.sort(key=lambda x: x[1])
  
  M = list[(N+1)//2-1][1]
  
  print(M-m+1)
else:
  list.sort()
  m = list[N//2-1][0]+list[N//2][0]
  list.sort(key=lambda x: x[1])
  M = list[N//2-1][1]+list[N//2][1]
  print(M-m+1)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
from collections import deque,defaultdict
import heapq
from itertools import combinations
import bisect

n=int(input())
l=[]
p=[]
q=[]
for i in range(n):
    a,b=map(int,input().split())
    l.append([2*a,2*b])
    p.append(2*a)
    q.append(2*b)
p.sort()
q.sort()
if n%2==0:
    al=(p[n//2]+p[n//2-1])//2
    ar=(q[n//2]+q[n//2-1])//2
else:
    al=p[n//2]//2
    ar=q[n//2]//2
print(ar-al+1)

Solution (Python):
n = int(input())
aa = [0]*n
bb = [0]*n
for i in range(n):
    aa[i], bb[i] = map(int, input().split())

def get_2med(arr):
    m = len(arr)
    ar = sorted(arr)
    if m%2 == 0:
        return ar[m//2-1] + ar[m//2]
    else:
        return ar[(m+1)//2-1]
    
minmed = get_2med(aa)
maxmed = get_2med(bb)
print(maxmed - minmed + 1)

Solution (Python):
N=int(input())
ab = [tuple(map(int, input().split())) for i in range(N)]
a,b = zip(*ab)
res = 0
ma = max(b)+1

def solve_left(idx):
    left = sum([1 for l,r in ab if idx<l])
    if left > N//2:
        return False
    return True

def solve_right(idx):
    right = sum([1 for l,r in ab if idx>r])
    if right > N//2:
        return False
    return True
def solve_left2(idx):
    left = sum([1 for l,r in ab if idx<l])
    if left > N//2-1:
        return False
    return True

def solve_right2(idx):
    right = sum([1 for l,r in ab if idx>r])
    if right > N//2-1:
        return False
    return True

ok = ma
ng = 0
while abs(ok-ng) > 1:
    cnt = (ok + ng) // 2
    if solve_left(cnt):
        ok = cnt
    else:
        ng = cnt
res_left = ok

ok = 0
ng = ma
while abs(ok-ng) > 1:
    cnt = (ok + ng) // 2
    if solve_right(cnt):
        ok = cnt
    else:
        ng = cnt
res_right = ok

if N%2==0:
    ok = ma
    ng = 0
    while abs(ok - ng) > 1:
        cnt = (ok + ng) // 2
        if solve_left2(cnt):
            ok = cnt
        else:
            ng = cnt
    res_left2 = ok
    
    ok = 0
    ng = ma
    while abs(ok - ng) > 1:
        cnt = (ok + ng) // 2
        if solve_right2(cnt):
            ok = cnt
        else:
            ng = cnt
    res_right2 = ok

if N%2==1:
    res = (res_right-res_left) + 1
else:
    
    res = (res_right+res_right2)-(res_left+res_left2) + 1
print(res)

Solution (Python):
import statistics
n=int(input())
A=[]
B=[]
for i in range(n):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)

median_min=statistics.median(A)
median_max=statistics.median(B)

if n%2!=0:
    ans=int(median_max-median_min+1)
else:
    ans=int(2*median_max-2*median_min+1)

print(ans)

Solution (Python):
n = int(input())
a = []
b = []

for i in range(n):
    aa,bb = map(int, input().split())
    a.append(aa)
    b.append(bb)

a.sort()
b.sort()

if n%2 == 1:
    p = a[n//2]
    q = b[n//2]
    ans = q - p + 1

else:
    p1 = a[n//2 -1]
    p2 = a[n//2]
    q1 = b[n//2]
    q2 = b[n//2 - 1]
    p = (p1+p2)*5
    q = (q1+q2)*5 
    ans = (q-p)//5 + 1

print(ans)

Solution (Python):
N = int(input())
A = []
B = []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)

A.sort()
B.sort()
if N % 2 == 0:
    j = N // 2
    i = j - 1
    med1_by_2 = A[i] + A[j]
    med2_by_2 = B[i] + B[j]
    ans = med2_by_2 - med1_by_2 + 1
else:
    i = N // 2
    med1 = A[i]
    med2 = B[i]
    ans = med2 - med1 + 1
print(ans)

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul
from decimal import Decimal

mod = 10 ** 9 + 7
INF = 10 ** 13
sys.setrecursionlimit(2147483647)
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]


n = I()
A = []
B = []
for _ in range(n):
    a, b = LI()
    A += [a]
    B += [b]

A.sort()
B.sort()
if n % 2:
    print(B[n // 2] - A[n // 2] + 1)
else:
    print((B[n // 2] + B[n // 2 - 1]) - (A[n // 2] + A[n // 2 - 1]) + 1)

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

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

if N%2==1:
    
    NG=-1
    OK=10**9+1

    while OK-NG>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if a<=mid:
                count+=1

            if count>=N//2+1:
                OK=mid
                break
        else:
            NG=mid

    MIN=OK

    OK=-1
    NG=10**9+1

    while NG-OK>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if b>=mid:
                count+=1

            if count>=N//2+1:
                OK=mid
                break
        else:
            NG=mid

    MAX=OK

    print(MAX-MIN+1)

else:
    
    NG=-1
    OK=10**9+1

    while OK-NG>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if a<=mid:
                count+=1

            if count>=N//2+1:
                OK=mid
                break
        else:
            NG=mid

    MIN0=OK

    NG=-1
    OK=10**9+1

    while OK-NG>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if a<=mid:
                count+=1

            if count>=N//2:
                OK=mid
                break
        else:
            NG=mid

    MIN1=OK

    OK=-1
    NG=10**9+1

    while NG-OK>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if b>=mid:
                count+=1

            if count>=N//2+1:
                OK=mid
                break
        else:
            NG=mid

    MAX0=OK

    OK=-1
    NG=10**9+1

    while NG-OK>1:
        mid=(OK+NG)//2

        count=0
        for a,b in K:
            if b>=mid:
                count+=1

            if count>=N//2:
                OK=mid
                break
        else:
            NG=mid

    MAX1=OK

    

    print(int(((MAX1+MAX0)/2-(MIN1+MIN0)/2)*2+1))

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

all_min=[]
all_max=[]
for itm in ab:
    a,b=itm
    all_min.append(a)
    all_max.append(b)

import statistics
med_min=statistics.median(all_min)
med_max=statistics.median(all_max)

diff = med_max - med_min

if n%2==0:
    print(int(diff*2+1))
else:
    print(diff+1)

Solution (Python):
import sys
def input():
	return sys.stdin.readline()[:-1]
n = int(input())
seg = [list(map(int, input().split())) for _ in range(n)]
a = [x[0] for x in seg]
b = [x[1] for x in seg]
a.sort()
b.sort()

if n%2 == 1:
	print(b[n//2] - a[n//2] + 1)
else:
	print(b[n//2] - a[n//2] + b[n//2-1] - a[n//2-1] + 1)

Solution (Python):
from statistics import median

N = int(input())
As = [0] * N
Bs = [0] * N

for i in range(N):
    As[i], Bs[i] = map(int, input().split())

med_A = median(As)
med_B = median(Bs)

if N%2:
    print(med_B-med_A+1)
else:
    print(int((med_B-med_A)*2)+1)

Solution (Python):
n = int(input())
a, b = [], []
for _ in range(n):
    u, v = map(int, input().split())
    a.append(u)
    b.append(v)
a.sort()
b.sort(reverse = True)
if n % 2 == 1:
    print(b[n // 2] - a[n // 2] + 1)
else:
    print(b[n // 2] + b[n // 2 - 1] - a[n // 2] - a[n // 2 - 1] + 1)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
N = int(input())
A, B = [], []
for _ in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A, B = sorted(A), sorted(B)
m1 = A[N//2] + A[(N-1)//2]
m2 = B[N//2] + B[(N-1)//2]
print((m2 - m1) // (N % 2 + 1) + 1)

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

minlst=[0]*N
maxlst=[0]*N

for i in range(N):
    minlst[i]=part[i][0]
    maxlst[i]=part[i][1]
minlst.sort()
maxlst.sort()

if N%2==1:
    left=minlst[(N+1)//2-1]
    right=maxlst[(N+1)//2-1]
else:
    left=minlst[N//2-1]+minlst[N//2]
    right=maxlst[N//2-1]+maxlst[N//2]

print(right-left+1)

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

X_l = sorted([Ai for Ai, Bi in AB])
X_r = sorted([Bi for Ai, Bi in AB])

if N % 2 == 0:
    ans_min = X_l[N // 2 - 1] + X_l[N // 2]
    ans_max = X_r[N // 2 - 1] + X_r[N // 2]
else:
    ans_min = X_l[N // 2]
    ans_max = X_r[N // 2]

ans = ans_max - ans_min + 1
print(ans)

Solution (Python):
def main():
    N = int(input())
    info = [tuple(map(int, input().split())) for _ in range(N)]

    A = [a for a, _ in info]
    B = [b for _, b in info]

    A.sort()
    B.sort()
    if N%2 == 0:
        min_median2 = A[N//2-1] + A[N//2]
        max_median2 = B[N//2-1] + B[N//2]
        ans = max_median2 - min_median2 + 1
    else:
        min_median2 = A[N//2]
        max_median2 = B[N//2]
        ans = max_median2 - min_median2 + 1

    print(ans)

    

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())
A = [0] * N
B = [0] * N
for i in range(N):
  a, b = list(map(int, input().split()))
  A[i] = a
  B[i] = b
  
A = sorted(A)
B = sorted(B)

if N % 2 == 1:
  x = int((N + 1)// 2)
  ans = abs(B[x - 1] - A[x - 1]) + 1
else:
  x = int(N // 2)
  a = A[x] + A[x - 1]
  b = B[x] + B[x - 1]
  
  ans = abs(b - a) + 1
  
print(ans)

Solution (Python):
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math

MOD = 10 ** 9 + 7


n = int(input())
P = [list(map(int, input().split())) for i in range(n)]

A = [e[0] for e in P]
B = [e[1] for e in P]
A.sort()
B.sort()

if n%2 == 1:
    piv = (n+1)//2
    start = A[piv-1]
    end = B[-piv]
    
    print(end - start + 1)
else:
    piv = n//2
    start = (A[piv-1] + A[piv])/2
    end = (B[-piv] + B[-piv-1])/2
    
    print(int((end - start)*2 + 1))

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

A = sorted(ab[0] for ab in AB)
B = sorted(ab[1] for ab in AB)

N2 = N//2
if N%2 == 1:
    print(B[N2] - A[N2] +1)
else:
    print((B[N2] + B[N2-1]) - (A[N2] + A[N2-1])+1)

Solution (Python):
N = int(input())
L = [tuple( map(int, input().split() ) ) for i in range(N) ]


A = [L[i][0] for i in range(N)]
A.sort()
B = [L[i][1] for i in range(N)]
B.sort()

if N % 2 == 1:
  m = A[(N-1)//2]
else: 
  m_2 = A[N//2 - 1] + A[N//2]
  
if N % 2 == 1:
  M = B[(N-1)//2]
else: 
  M_2 = B[N//2 - 1] + B[N//2]
  
  

if N % 2 == 1:
  print(M-m+1)
else:
  print(M_2 - m_2 + 1)

Solution (Python):
n = int(input())
AB = [list(map(int, input().split())) for _ in range(n)]
A, B = zip(*AB)
A = sorted(A)
B = sorted(B)
if n%2:
    a_m = A[(n-1)//2]
    b_m = B[(n-1)//2]
else:
    a_m = A[n//2] + A[n//2 - 1]
    b_m = B[n//2] + B[n//2 - 1]
ans = b_m - a_m + 1
print(ans)

Solution (Python):

N=int(input())
A=[]
B=[]
for i in range(N):
    a,b=map(int,input().split())
    A.append(a)
    B.append(b)
A.sort()
B.sort()
if N%2==1:
    print(B[N//2]-A[N//2]+1)
else:
    print(B[N//2-1]-A[N//2-1]+B[N//2]-A[N//2]+1)

Solution (Python):
n = int(input())
a = []
b = []
for i in range(n):
  aa,bb = map(int,input().split())
  a.append(aa)
  b.append(bb)
a.sort()
b.sort()
if n%2 == 1:
  print(b[n//2]-a[n//2]+1)
else:
  print(b[n//2]+b[n//2-1]-a[n//2]-a[n//2-1]+1)

Solution (Python):
n = int(input())
a = []
b = []
for _ in range(n):
    a_, b_ = map(int, input().split())
    a.append(a_)
    b.append(b_)
a.sort()
b.sort()
if n%2:
    print(b[n//2] - a[n//2] + 1)
else:
    print(b[n//2]+b[n//2-1] - a[n//2]-a[n//2-1] + 1)

Solution (Python):
from statistics import median as m
n=int(input())
a=[0]*n
b=[0]*n
for i in range(n):
  x,y=map(int,input().split())
  a[i]=x
  b[i]=y
x=m(a)
y=m(b)
if n%2==0:
  x*=2
  y*=2
print(int(y-x+1))

Solution (Python):
import statistics
N = int(input())
AB = [[a,b] for a,b in (map(int,input().split()) for _ in range(N))]

A,B = zip(*AB)
A = list(A)
B = list(B)
A.sort()
B.sort()
medianA = statistics.median(A)
medianB = statistics.median(B)
if N%2 == 0:
    ans = (medianB-medianA)/0.5+1
else:
    ans = medianB-medianA+1
print(int(ans))

Solution (Python):
N = int(input())
A = []
B = []
for i in range(N):
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)
A.sort()
B.sort()
if N % 2 == 0:
    b = (B[N//2-1]+B[N//2])/2
    a = (A[N//2-1]+A[N//2])/2
    ans = (b-a)//0.5 +1
else:
    b = B[(N+1)//2-1]
    a = A[(N+1)//2-1]
    ans = b-a+1
print(int(ans))

Solution (Python):
N = int(input())
from  statistics import median


MIN = [0] * N
MAX = [0] * N

for i in range(N):
  A, B = map(int, input().split())
  
  MIN[i] = A
  MAX[i] = B
  
min_ = median(MIN)
max_ = median(MAX)
d = max_ - min_

if N % 2 == 0:
  print(int(d * 2) + 1)
else:
  print(int(d)+1)

Solution (Python):
n = int(input())
adat = []
bdat = []
for _ in range(n):
    a,b = map(int, input().split())
    adat.append(a)
    bdat.append(b)
adat.sort()
bdat.sort()

if n % 2 == 1:
    aa = adat[n//2]
    bb = bdat[n//2]
    print(bb-aa + 1)

else:
    aa1 = adat[n//2-1]
    aa2 = adat[n//2]
    bb1 = bdat[n//2-1]
    bb2 = bdat[n//2]
    
    aaa = (aa1+aa2) / 2
    bbb = (bb1+bb2) / 2
    cnt = bbb - aaa
    cnt = cnt // 0.5
    print(int(cnt + 1))

Solution (Python):

import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N = ir()
AB = np.array([lr() for _ in range(N)])
A = AB[:, 0]
B = AB[:, 1]
me_A = np.median(A)
me_B = np.median(B)
if N&1:
    answer = int(me_B - me_A) + 1
else:
    answer = int((me_B - me_A) / 0.5) + 1

print(answer)

Solution (Python):
n = int(input())
a, b = [], []
lst = []
for i in range(1, n+1):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
    lst.append([ai, bi, i])

if n % 2 == 1:
    a.sort()
    b.sort()
    idx = n//2
    print(b[idx]-a[idx]+1)
    exit()

a.sort()
b.sort()
mini = (a[n//2]+a[n//2-1])/2
maxi = (b[n//2]+b[n//2-1])/2
print(int((maxi-mini)*2+1))

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

if N % 2 == 0:
    n0 = N // 2 - 1
    n1 = n0 + 1
else:
    n0 = (N + 1) // 2 - 1
    n1 = n0


X.sort()
l0 = X[n0][0]
l1 = X[n1][0]
Ls, Lt = divmod(l0 + l1, 2)


X.sort(key=lambda x: x[1])
r0 = X[n0][1]
r1 = X[n1][1]
Rs, Rt = divmod(r0 + r1, 2)

e = 2 if N % 2 == 0 else 1
d = (Rs * e) - (Ls * e) + 1
cnt = d
cnt -= (Lt == 1)
cnt += (Rt == 1)
print(cnt)

Solution (Python):
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
if N % 2 == 1:
    p = sorted(a)[N // 2][0]
    q = sorted(a, key = lambda x: x[1])[N // 2][1]
    print(q - p + 1)
else:
    a = sorted(a)
    p1 = a[N // 2 - 1][0]
    p2 = a[N // 2][0]
    a = sorted(a, key = lambda x: x[1])
    q1 = a[N // 2 - 1][1]
    q2 = a[N // 2][1]
    print(q1 + q2 - p1 - p2 + 1)

Solution (Python):
import sys
import heapq
import random
import collections
import math





def solve(grid):  

    a,b = zip(*grid)
    a = sorted(a)
    b = sorted(b)
    
    if len(a)%2 == 1:
        return b[len(a)//2] - a[len(a)//2] + 1

    lb = (a[len(a)//2] + a[len(a)//2-1])/2
    ub = (b[len(a)//2] + b[len(a)//2-1])/2
    
    return int(2 * (ub - lb) + 1)


def console(*args):  
    print('\033[36m', *args, '\033[0m', file=sys.stderr)
    return



    
    

    
nrows = int(input())










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

res = solve(grid)  





print(res)

Solution (Python):
n = int(input())

AB = []
for _ in range(n):
    ab = tuple(map(int, input().split()))
    AB.append(ab)

AB_A = sorted(AB, key=lambda x: x[0])
AB_B = sorted(AB, key=lambda x: x[1])

if n%2==1:
    sa, sb = AB_A[n//2]
    la, lb = AB_B[n//2]
    print(lb - sa + 1)
else:
    sal, sbl = AB_A[n//2-1]
    sar, sbr = AB_A[n//2]

    lal, lbl = AB_B[n//2-1]
    lar, lbr = AB_B[n//2]
    print((lbl + lbr) - (sal + sar) +1)

Solution (Python):
N = int(input())
A = []
B = []
for i in range(N):
    Ai, Bi = map(int, input().split())
    A.append(Ai)
    B.append(Bi)

A.sort()
B.sort()
if N % 2 == 0:
    ans = sum(B[N // 2 - 1:N // 2 + 1]) - sum(A[N // 2 - 1:N // 2 + 1]) + 1
else:
    ans = B[N // 2] - A[N // 2] + 1
print(ans)

Solution (Python):
n=int(input())
a=[None]*n
b=[None]*n
for i in range(n):
    a[i],b[i] = map(int,input().split())

a.sort()
b.sort()
if n%2==1:
    ans=b[n//2]-a[n//2]+1
else:
    ans = (b[n//2] +b[n//2-1]) - (a[n//2] +a[n//2-1]) +1
print(ans)