Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
import numpy as np

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

N, A, B = lr()
MOD = 10 ** 9 + 7

def cmb(n, k):
    if k > n:
        return 0
    return fact[n] * fact_inv[k] % MOD * fact_inv[n-k] % MOD

def cumprod(arr, MOD):
    L = len(arr); Lsq = int(L**.5+1)
    arr = np.resize(arr, Lsq**2).reshape(Lsq, Lsq)
    for n in range(1, Lsq):
        arr[:, n] *= arr[:, n-1]; arr[:, n] %= MOD
    for n in range(1, Lsq):
        arr[n] *= arr[n-1, -1]; arr[n] %= MOD
    return arr.ravel()[:L]

def make_fact(U, MOD):
    x = np.arange(U, dtype=np.int64); x[0] = 1
    fact = cumprod(x, MOD)
    x = np.arange(U, 0, -1, dtype=np.int64); x[0] = pow(int(fact[-1]), MOD-2, MOD)
    fact_inv = cumprod(x, MOD)[::-1]
    return fact, fact_inv

def power_func(a,n,p):
    bi=str(format(n,"b"))#2進表現に
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res

U = N+1 # 階乗テーブルの上限
fact, fact_inv = make_fact(U, MOD)
answer = power_func(2, N, MOD) - 1 - cmb(N, A) - cmb(N, B)
print(answer%MOD)

Fixed submission:
import sys
from functools import reduce

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

N, A, B = lr()
MOD = 10 ** 9 + 7

def F(A):
    num = reduce(lambda x, y: x * y % MOD, range(N, N-A, -1))
    den = reduce(lambda x, y: x * y % MOD, range(1, A+1))
    return num * pow(den, MOD-2, MOD) % MOD

answer = pow(2, N, MOD) - F(A) - F(B) - 1
print(answer % MOD)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
import numpy as np

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

N, K = lr()
A = lr()
A_np = np.array(A)
product = []
for i in range(N-1):
    l = A[i] * A_np[i+1:]
    product.extend(l)

product.sort()
print(product[K-1])


Fixed submission:
import sys
import numpy as np

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

N, K = lr()
A = np.array(lr())
A.sort()
pos = A[A>0]
zero = A[A==0]
neg = A[A<0]

def check(x):
    # x以下の数がK個以上ある時、Trueを返す
    count = 0 #最後に２で割る
    if x >= 0:
        count += len(zero) * N
    count += (np.searchsorted(A, x//pos, side='right')).sum()
    count += (N - np.searchsorted(A, (-x-1)//(-neg), side='right')).sum()
    count -= np.count_nonzero(A * A <= x) #ペアなので自分自身は駄目
    assert count % 2 == 0
    count //= 2
    return count >= K

left = - 10 ** 19 # NG
right = 10 ** 19 # OK
while right > left + 1:
    mid = (left+right) // 2
    if check(mid):
        right = mid
    else:
        left = mid

print(right)
# 46
Buggy python submission (verdict: Runtime Error):
# coding: utf-8
import sys
import numpy as np

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

N, K = lr()
P = np.array(lr(), np.float64)
P += 1; P /= 2
P = [0] + P
Pcum = P.cumsum()
expectation = Pcum[K:] - Pcum[:-K]
answer = expectation.max()
print(answer)


Fixed submission:
import sys
import numpy as np

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

N, K = lr()
P = np.array([0] + lr())
P = (P+1) / 2
Pcum = P.cumsum()
X = Pcum[K:] - Pcum[:-K]
answer = X.max()
print(answer)

Buggy python submission (verdict: Runtime Error):
# coding: utf-8
import sys
import numpy as np

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

N, K = lr()
P = np.array(lr(), np.float32)
P += 1; P /= 2
P = [0] + P
Pcum = P.cumsum()
expectation = Pcum[K:] - Pcum[:-K]
answer = expectation.max()
print(answer)


Fixed submission:
import sys
import numpy as np

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

N, K = lr()
P = np.array([0] + lr())
P = (P+1) / 2
Pcum = P.cumsum()
X = Pcum[K:] - Pcum[:-K]
answer = X.max()
print(answer)

Buggy python submission (verdict: Runtime Error):
# coding: utf-8
import sys
import numpy as np

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

N, K = lr()
P = np.array(lr(), np.float32)
P += 1; P /= 2
P = [0] + P
print(P)
Pcum = P.cumsum()
expectation = Pcum[K:] - Pcum[:-K]
answer = expectation.max()
print(answer)


Fixed submission:
import sys
import numpy as np

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

N, K = lr()
P = np.array([0] + lr())
P = (P+1) / 2
Pcum = P.cumsum()
X = Pcum[K:] - Pcum[:-K]
answer = X.max()
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
import sys

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

# dp[i+1][j] i番目までの魔法を使ってモンスターへの攻撃jにする魔力の最小値
# (j=0の時まだ攻撃していない)
H, N = lr()
INF = 10 ** 10
dp = [INF] * (H+10**4+10)
dp[0] = 0
for i in range(N):
    a, b = lr()
    for j in range(a, H+a+1):
        if dp[j-a] == INF:
            continue
        dp[j] = min(dp[j], dp[j-a] + b)

answer = min(dp[H:])
print(answer)


Fixed submission:
import sys

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

# dp[i+1][j] i番目までの魔法を使ってモンスターへの攻撃jにする魔力の最小値
# (j=0の時まだ攻撃していない)
H, N = lr()
INF = 10 ** 10
dp = [INF] * (H+10**4+10)
dp[0] = 0
for i in range(N):
    a, b = lr()
    for j in range(a, H+a+1):
        if dp[j-a] == INF:
            continue
        dp[j] = min(dp[j], dp[j-a] + b)

answer = min(dp[H:])
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import sys

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

# dp[i+1][j] i番目までの魔法を使ってモンスターへの攻撃jにする魔力の最小値
# (j=0の時まだ攻撃していない)
H, N = lr()
INF = 10 ** 10
dp = [[INF] * (H+10**4+10) for _ in range(N+1)]
dp[0][0] = 0
for i in range(N):
    a, b = lr()
    dp[i+1] = dp[i]
    for j in range(1, H+a+1):
        dp[i+1][j] = min(dp[i+1][j], dp[i+1][j-a] + b)

answer = min(dp[N][H:])
print(answer)


Fixed submission:
import sys

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

# dp[i+1][j] i番目までの魔法を使ってモンスターへの攻撃jにする魔力の最小値
# (j=0の時まだ攻撃していない)
H, N = lr()
INF = 10 ** 10
dp = [INF] * (H+10**4+10)
dp[0] = 0
for i in range(N):
    a, b = lr()
    for j in range(a, H+a+1):
        if dp[j-a] == INF:
            continue
        dp[j] = min(dp[j], dp[j-a] + b)

answer = min(dp[H:])
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8
import sys
from collections import deque

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

# 左からgreedyに
N, D, A = lr()
monsters = []
for _ in range(N):
    x, h = lr()
    monsters.append((x, h))

monsters.sort()
bomb = deque()
answer = 0
for x, h in monsters:
    while bomb:
        if bomb[0][0] + D < x:
            bomb.popleft()
        else:
            break
    for place, time in bomb:
        h -= A * time
    if h > 0:
        t = -(-h//A)
        answer += t
        bomb.append((x + D, t))

print(answer)    


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

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

N, D, A = lr()
XH = [lr() for _ in range(N)]
XH.sort()

over = [N] * N # over[i]はi番目のモンスターを攻撃した時影響のないモンスターの最小値（最大はNで対象なし）
cur = 1
for i in range(N):
    while cur < N and XH[i][0] + D + D >= XH[cur][0]:
        cur += 1
    over[i] = cur

damage = 0 # 今までの累計のダメージ数　(影響のないダメージは引く)
reset = [0] * (N+1) # これ以降関係のないダメージ
answer = 0
for i in range(N):
    x, h = XH[i]
    damage -= reset[i]
    h -= damage
    if h > 0:
        time = (h+A-1)//A
        answer += time
        damage += A * time
        reset[over[i]] += A * time

print(answer)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 7)

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

N, D, A = lr()
XH = [lr() for _ in range(N)]
XH.sort(key=lambda x:x[0])

over = [N] * (N+1) # over[i]はi番目のモンスターを攻撃した時影響のないモンスターの最小値（最大はNで対象なし）
cur = 1
for i in range(N):
    while cur <= N and XH[i][0] + D + D >= XH[cur][0]:
        cur += 1
    over[i] = cur

damage = 0 # 今までの累計のダメージ数　(影響のないダメージは引く)
reset = [0] * (N+1) # 対象のモンスターの影響しなかったダメージ
answer = 0
for i in range(N):
    x, h = XH[i]
    damage -= reset[i]
    h = h - damage
    time = (h+A-1)//A
    answer += time
    damage += A * time
    reset[over[i]] += A * time

print(answer)
# 00


Fixed submission:
import sys
sys.setrecursionlimit(10 ** 7)

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

N, D, A = lr()
XH = [lr() for _ in range(N)]
XH.sort()

over = [N] * N # over[i]はi番目のモンスターを攻撃した時影響のないモンスターの最小値（最大はNで対象なし）
cur = 1
for i in range(N):
    while cur < N and XH[i][0] + D + D >= XH[cur][0]:
        cur += 1
    over[i] = cur

damage = 0 # 今までの累計のダメージ数　(影響のないダメージは引く)
reset = [0] * (N+1) # これ以降関係のないダメージ
answer = 0
for i in range(N):
    x, h = XH[i]
    damage -= reset[i]
    h -= damage
    if h > 0:
        time = (h+A-1)//A
        answer += time
        damage += A * time
        reset[over[i]] += A * time

print(answer)
Buggy python submission (verdict: Runtime Error):
import sys

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

N, M = lr()
problems = [False] * N
AC = [0] * N
WA = [0] * N
for _ in range(M):
    p, S = sr().split(); p = int(p) - 1
    if not problems[p] and S == 'WA':
        WA[p] += 1
    if not problems[p] and S == 'AC':
        problems[p] = True
        AC += 1

AC_total = sum(AC)
WA_total = sum(y for x, y in zip(AC, WA) if x)
print(AC_total, WA_total)


Fixed submission:
import sys
#import numpy as np

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
solve = [False] * (N+1)
count = [0] * (N+1)
penalty = 0
for i in range(M):
    p, s = input().split()
    p = int(p)
    if solve[p]:
        continue
    if s == 'WA':
        count[p] += 1
    else:
        solve[p] = True
        penalty += count[p]

print(sum(solve), penalty)
Buggy python submission (verdict: Runtime Error):
import sys

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

# A が2で何回割れるか
N, M = lr()
A = lr()
A = [x // 2 for x in A]
cnt = 0
while all(x%2 == 0 for x in A):
    cnt += 1
    A = [x // 2 for x in A]

if any(x%2 == 0 for x in A):
    print(0); exit()
lcm = 1
for a in A:
    lcm *= a // gcd(lcm, a)

answer = M // lcm - M // (2 * lcm)
print(answer)
# 21

Fixed submission:
import sys
import numpy as np
from fractions import gcd
from functools import reduce

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split())) # applies to numbers only
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M = rl()
A = np.array(rl())
B = A // 2

def merge(a, b):
    g = gcd(a, b)
    a //= g; b //= g
    if a%2 == 0 or b%2 == 0:
        return 0
    n = g * a * b
    if n > 10 ** 9:
        return 0
    return n

x = reduce(merge, B)
if x == 0:
    answer = 0
else:
    answer = M // x - M // (2*x)

print(answer)
Buggy python submission (verdict: Runtime Error):
stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N = ri()

if N&1:
    print(0)
    exit()

answer = N // 10

while N >= 50:
    answer += (N // 50)
    N //= 50
print(answer)

Fixed submission:
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N = ri()

if N&1:
    print(0)
    exit()

answer = N // 10
x = 50
while N >= x:
    answer += (N // x)
    x *= 5
print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 上限は1000
N = ri()
S = list(rs())
answer = set()

for i in range(len(S)-2):
    se2 = set()
    for j in range(i+1, len(S)-1):
        if j in se2:
            continue
        se2.add(j)
        se = set(S[j+1:])
        x = S[i]
        y = S[j]
        for z in se:
            answer.add((x, y, z))

print(len(answer))

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 上限は1000
N = ri()
S = list(rs())
answer = set()
se1 = set()
for i in range(len(S)-2):
    x = S[i]
    if x in se1:
        continue
    se1.add(x)
    se2 = set()
    for j in range(i+1, len(S)-1):
        y = S[j]
        if y in se2:
            continue
        se2.add(y)
        se = set(S[j+1:])
        for z in se:
            answer.add((x, y, z))

print(len(answer))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 上限は1000
N = ri()
S = list(rs())
answer = set()

for i in range(len(S)-2):
    for j in range(i+1, len(S)-1):
        se = set(S[j+1:])
        for x in se:
            answer.add((S[i], S[j], x))
        #print(i, j, len(answer))

print(len(answer))

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

# 上限は1000
N = ri()
S = list(rs())
answer = set()
se1 = set()
for i in range(len(S)-2):
    x = S[i]
    if x in se1:
        continue
    se1.add(x)
    se2 = set()
    for j in range(i+1, len(S)-1):
        y = S[j]
        if y in se2:
            continue
        se2.add(y)
        se = set(S[j+1:])
        for z in se:
            answer.add((x, y, z))

print(len(answer))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

T1, T2 = rl()
A1, A2 = rl()
B1, B2 = rl()

A1 = (A1 - B1) * T1
A2 = (A2 - B2) * T2
#print(A1, A2)
if A1 + A2 == 0:
    print('infinity')
    exit()
if A1 * (A1 + A2) > 0:
    print(0)
    exit()
cur = 0
answer = -1
while True:
    cur1 = cur + A1
    if cur * cur1 <= 0:
        answer += 1
    else:
        break
    if cur1 == 0:
        break
    cur = cur1
    cur2 = cur + A2
    if cur * cur2 <= 0:
        answer += 1
    else:
        break
    if cur2 == 0:
        break
    cur = cur2
print(answer)

Fixed submission:
import sys
sys.setrecursionlimit(10 ** 9)

stdin = sys.stdin
 
ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))
rs = lambda: stdin.readline().rstrip()  # ignore trailing spaces

T1, T2 = rl()
A1, A2 = rl()
B1, B2 = rl()

if T1 * A1 + T2 * A2 == T1 * B1 + T2 * B2:
    print('infinity')
    exit()
if (A1 > B1 and A1 * T1 + A2 * T2 > B1 * T1 + B2 * T2) or \
        (A1 < B1 and A1 * T1 + A2 * T2 < B1 * T1 + B2 * T2):
    print(0)
    exit()
diff = abs(A1-B1) * T1
diff2 = abs(T1 * A1 + T2 * A2 - (T1 * B1 + T2 * B2))
x, y = divmod(diff, diff2)
print(x * 2 if y == 0 else x * 2 + 1)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
graph = [[] for i in range(N+1)] #graph[0]は使わない
edges = [list(map(int, input().split())) for _ in range(N-1)]

for i in range(N-1):
    a, b = edges[i]
    graph[a].append(b)
    graph[b].append(a)

colors = 1
for g in graph:
    colors = max(colors, len(g))
#colorsの数は決定
print(colors)

used = [set() for i in range(N+1)]
cur = 1

for a, b in edges:
    while cur in used[a] or cur in used[b]:
        cur += 1
        if cur > colors:
            cur = 1
    print(cur)
    used[a].add(cur)
    used[b].add(cur)


Fixed submission:
import sys

stdin = sys.stdin
 
ni = lambda:int(ns())
na = lambda:list(map(int,stdin.readline().split()))
ns = lambda:stdin.readline().rstrip()  # ignore trailing spaces

N = ni()
AB = [na() for _ in range(N-1)]
graph = [[] for _ in range(N+1)]

for a, b in AB:
    graph[a].append(b)
    graph[b].append(a)

root = 1
parent = [0] * (N+1)
order = []
stack = [root]

while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if y == parent[x]:
            continue
        parent[y] = x
        stack.append(y)

color = [-1] * (N+1)
for o in order:
    ng = color[o]
    c = 1
    for y in graph[o]:
        if y == parent[o]:
            continue
        if c == ng:
            c += 1
        color[y] = c
        c += 1
answer = []
append = answer.append
for a, b in AB:
    if parent[a] == b:
        append(color[a])
    else:
        append(color[b])
print(max(answer))
print('\n'.join(map(str,answer)))
Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

S = list(input())
l = len(S) + 1
A = np.zeros(l, dtype=np.int16)
B = np.zeros(l, dtype=np.int16)

for i in range(len(S)):
    if S[i] == '<':
        A[i+1] = A[i] + 1

for i in range(len(S)-1, -1, -1):
    if S[i] == '>':
        B[i] = B[i+1] + 1
answer = (np.maximum(A, B)).sum()
print(answer)

Fixed submission:
S = list(input())
A = [0] * (len(S)+1)
imos = [0] * (len(S))
for i in range(len(S)):
    if S[i] == '>':
        imos[i] = 1
    else:
        imos[i] = -10000000
imos += [0]
for i in range(len(S), 0, -1):
    imos[i-1] = max(0, imos[i-1] + imos[i])
A[0] = imos[0]
for i in range(len(S)):
    if S[i] == '<':
        A[i+1] = max(imos[i+1], A[i]+1)
    else:
        A[i+1] = max(0, min(A[i]-1, imos[i+1]))
print(sum(A))
Buggy python submission (verdict: Runtime Error):
# 一番長いLRが最低の楽しさ
# 一番長いLRと重なるのが一番少ないものはもう一つにする
# 一番長いLRが最低の楽しさ 一番長いLRが複数ある場合どうする？
# 一番長いLRと重なるのが一番少ないものはもう一つにする
N = int(input())
LR = [list(map(int, input().split())) for _ in range(N)][::-1]
LR.sort(key=lambda x: x[1]-x[0], reverse=True)
ma = LR[0][1] - LR[0][0] + 1
left_ma = LR[0][0]
right_ma = LR[0][1]

ma2 = ma
another = 10 ** 9
another_length = 0 #重なっていない長さ
LR.pop(0)

another_length = LR[1][1] - LR[1][0] + 1
left_an = LR[1][0]
right_an = LR[1][1]

point = ma + another_length
LR.pop(1)
for l, r in LR:
    if max(0, min(right_ma, r) - max(left_ma, l)) + another_length < ma + max(0, min(right_an, r) - max(left_an, l)):
        # anotherのグループにいれる
        another_length = max(0, min(right_an, r) - max(left_an, l) + 1)
        point = ma + another_length
        right_an = min(r, right_an)
        left_an = max(l, left_an)
        #print(right_an, left_an)
    else:
        ma = max(0, min(right_ma, r) - max(left_ma, l) + 1)
        point = ma + another_length
        right_ma = min(r, right_ma)
        left_ma = max(l, left_ma)

print(max(ma2, point))


Fixed submission:
import sys

stdin = sys.stdin

ri = lambda: int(rs())
rl = lambda: list(map(int, stdin.readline().split()))  # applies to only numbers
rs = lambda: stdin.readline().rstrip()  # ignores trailing space

N = ri()
L = []
R = []

for _ in range(N):
    l, r = rl()
    L.append(l)
    R.append(r)

max_l = max(L)
min_r = min(R)
ab = [(max(0, r - max_l + 1), max(0, min_r - l + 1)) for l, r in zip(L, R)]
ab.sort()
mi = float('inf')
answer = max(r - l + 1 for l, r in zip(L, R)) + max(0, min_r - max_l + 1)
for i in range(N - 1):
    mi = min(mi, ab[i][1])
    # miは第１グループの人数
    answer = max(answer, mi + ab[i + 1][0])
print(answer)
Buggy python submission (verdict: Runtime Error):
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))
A = np.sort(A)[::-1]
F = np.sort(F)
# 二部探索法　Aの最大値をどこまで減らせるか
if A.sum() <= K:
    print(0)
    exit()
if K == 0:
    print((A * F).max())
up = (A * F).max() # 可能 mid は完食にかかる時間
low = 0 # 不可能
while up > low + 1:
    mid = (up + low) // 2
    if (A - min(A, (mid // F))).sum() <= K: #可能
        up = mid
    else:
        low = mid
print(up)

Fixed submission:
import numpy as np
N, K = map(int, input().split())
A = np.array(list(map(int, input().split())))
F = np.array(list(map(int, input().split())))
A = np.sort(A)[::-1]
F = np.sort(F)
# 二部探索法　Aの最大値をどこまで減らせるか
if A.sum() <= K:
    print(0)
    exit()
if K == 0:
    print((A * F).max())
up = (A * F).max() # 可能 mid は完食にかかる時間
low = 0 # 不可能
while up > low + 1:
    mid = (up + low) // 2
    if (A - np.minimum(A, (mid // F))).sum() <= K: #可能
        up = mid
    else:
        low = mid
print(up)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from bisect import bisect_left

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

N = ir()
L = lr()
L.sort()
answer = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        candidate = L[j+1:]
        index = bisect_left(candidate, (L[i]+L[j]))
        answer += index

print(answer)


Fixed submission:
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect_left(L[j+1:], L[i]+L[j])
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect_left(L[j+1:], L[i]+L[j])
print(answer)


Fixed submission:
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect_left(L[j+1:], L[i]+L[j])
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect.bisect_left(L[j+1:], L[i]+L[j])
print(answer)

Fixed submission:
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect_left(L[j+1:], L[i]+L[j])
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
import numpy as np

N = int(input())
L = np.array(list(map(int, input().split())))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += sum(L[j+1:] < (L[i]+L[j]))
print(answer)

Fixed submission:
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect_left(L[j+1:], L[i]+L[j])
print(answer)

Buggy python submission (verdict: Time Limit Exceeded):
from itertools import combinations

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for x, y, z in list(combinations(L, 3)):
    if x + y > z:
        answer += 1
print(answer)

Fixed submission:
from bisect import bisect_left

N = int(input())
L = list(map(int, input().split()))
L.sort()
answer = 0
for i in range(N):
    for j in range(i+1, N):
        answer += bisect_left(L[j+1:], L[i]+L[j])
print(answer)