Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

fact2 = [0] * 1000011
def cnt2(n):
    if n%2 == 1:
        return 0
    else:
        fact2[n] = 1 + fact2[n//2]
        return fact2[n]

factorial = [0,0]
for i in range(2,1000010):
    factorial.append(factorial[-1] + cnt2(i))

def nck(n,k):
    return factorial[n] - factorial[k] - factorial[n - k]

def nxor(x,n):
    if n > 0:
        return 0
    else:
        return x


def main():
    n = int(input())
    a = [int(i) - 1 for i in list(input())]
    
    cumxor = 0
    amod = [i%2 for i in a]
    for i in range(n):
        cumxor ^= nxor(amod[i],nck(n - 1,i))
    
    if cumxor == 1:
        ans = 1
    else:
        if 1 in a:
            ans = 0
        else:
            cumxor = 0
            adiv = [a//2 for i in a]
            for i in range(n):
                cumxor ^= nxor(adiv[i],nck(n - 1,i))
            if cumxor == 0:
                ans = 0
            else:
                ans = 2
    
    print(ans)

if __name__=='__main__':
    main()

Fixed submission:
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

fact2 = [0] * 1000011
def cnt2(n):
    if n%2 == 1:
        return 0
    else:
        fact2[n] = 1 + fact2[n//2]
        return fact2[n]

factorial = [0,0]
for i in range(2,1000010):
    factorial.append(factorial[-1] + cnt2(i))

def nck(n,k):
    return factorial[n] - factorial[k] - factorial[n - k]

def nxor(x,n):
    if n > 0:
        return 0
    else:
        return x


def main():
    n = int(input())
    a = [int(i) - 1 for i in list(input())]
    
    cumxor = 0
    amod = [i%2 for i in a]
    for i in range(n):
        cumxor ^= nxor(amod[i],nck(n - 1,i))
    
    if cumxor == 1:
        ans = 1
    else:
        if 1 in a:
            ans = 0
        else:
            cumxor = 0
            adiv = [i//2 for i in a]
            for i in range(n):
                cumxor ^= nxor(adiv[i],nck(n - 1,i))
            if cumxor == 0:
                ans = 0
            else:
                ans = 2
    
    print(ans)

if __name__=='__main__':
    main()
Buggy python submission (verdict: Runtime Error):
def main():
    n,a,b=map(int,input().split())
    t=n//(a+b)
    ans=a*t+min(n%(t*(a+b)),a)
    print(ans)

if __name__=='__main__':
    main()

Fixed submission:
def main():
    n,a,b=map(int,input().split())
    if a==0:
        ans=0
    else:
        t=n//(a+b)
        if t==0:
            ans=min(a,n)
        else:
            ans=a*t+min(n%(t*(a+b)),a)
    print(ans)

if __name__=='__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
poll=[input() for i in range(n)]
poll2=list(set(poll))

dic={poll2[i]:0 for i in range(len(poll2))}
for string in poll:
    dic[string]+=1

max_k=[k for k, v in dic.items() if v == max(dic.values())]
max_k.sort()
print(*max_k,sep='\n')

Fixed submission:
def main():
  n=int(input())
  poll=[input() for i in range(n)]

  dic={}
  for string in poll:
    if string not in dic:
      dic[string]=1
    else:
      dic[string]+=1
  
  x=max(dic.values()) 
  max_k=[k for k, v in dic.items() if v==x]
  max_k.sort()
  print(*max_k,sep='\n')
  
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
poll=[input() for i in range(n)]
poll2=list(set(poll))

dic={poll2[i]:0 for i in range(len(poll2))}
for string in poll:
    dic[string]+=1

max_k=[k for k, v in dic.items() if v == max(dic.values())]
max_k.sort()
print(*max_k,sep='\n')

Fixed submission:
def main():
  n=int(input())
  poll=[input() for i in range(n)]

  dic={}
  for string in poll:
    if string not in dic:
      dic[string]=1
    else:
      dic[string]+=1
  
  x=max(dic.values()) 
  max_k=[k for k, v in dic.items() if v==x]
  max_k.sort()
  print(*max_k,sep='\n')
  
if __name__=='__main__':
  main()

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
poll=[input() for i in range(n)]

dic={}
for string in poll:
  if string not in dic:
    dic[string]=1
  else:
    dic[string]+=1

max_k=[k for k, v in dic.items() if v == max(dic.values())]
max_k.sort() 
print(*max_k,sep='\n')

Fixed submission:
def main():
  n=int(input())
  poll=[input() for i in range(n)]

  dic={}
  for string in poll:
    if string not in dic:
      dic[string]=1
    else:
      dic[string]+=1
  
  x=max(dic.values()) 
  max_k=[k for k, v in dic.items() if v==x]
  max_k.sort()
  print(*max_k,sep='\n')
  
if __name__=='__main__':
  main()
Buggy python submission (verdict: Time Limit Exceeded):
from  bisect import bisect

n,d,a=map(int,input().split())
monster=[list(map(int,input().split())) for i in range(n)]
monster.sort(key=lambda i:i[0])
r=[monster[i][0] for i in range(n)]
hp=[monster[i][1] for i  in range(n)]

#print(r,hp)
i,ans=0,0
while i<n:
  #print(i)
  s=hp[i]
  #print(s)
  if s>0:
    cnt=(s+a-1)//a
    #print(cnt)
    ans+=cnt
    damage=cnt*a
    #print(damage)
    for j in range(i,min(bisect(r,r[i]+2*d),n)):
      hp[j]-=damage
  #print(hp)
  i+=1
print(ans)


Fixed submission:
from  bisect import bisect

n,d,a=map(int,input().split())
monster=[list(map(int,input().split())) for i in range(n)]
monster.sort(key=lambda i:i[0])
r=[monster[i][0] for i in range(n)]
hp=[monster[i][1] for i  in range(n)]
#print(r,hp)

d=2*d
i,ans,damages=0,0,[0]*n
while i<n:
  if i>0:
    damages[i]+=damages[i-1]
    s=hp[i]+damages[i]
  else:
    s=hp[i]
  if s>0:
    cnt=(s+a-1)//a
    ans+=cnt
    #print(ans)
    damage=cnt*a
    damages[i]-=damage
    zone=bisect(r,r[i]+d)
    if zone<n:
      damages[zone]+=damage 
  i+=1
  #print(damages)
  #print(hp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
num=[int(i) for i in input().split()]

ch=[set(list(range(1,i+2))) for i in range(n)]
#print(ch)
ans=1
s={num[0]}
st=set()
for i in range(1,n):
  #print(s)
  if ch[num[i]-1] & s == st:
    ans+=1
  s.add(num[i])
#print(set(list(range(8))))
print(ans)

Fixed submission:
n=int(input())
num=[int(i) for i in input().split()]

ans=1
ch=num[0]
for i in range(1,n):
  if  num[i]<=ch:
    ans+=1
  ch=min(ch,num[i])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
num=[int(i) for i in input().split()]

ans=1
s={num[0]}
st=set()
for i in range(1,n):
  #print(s)
  if set(list(range(1,num[i]))) & s == st:
    ans+=1
  s.add(num[i])
#print(set(list(range(8))))
print(ans)
  

Fixed submission:
n=int(input())
num=[int(i) for i in input().split()]

ans=1
ch=num[0]
for i in range(1,n):
  if  num[i]<=ch:
    ans+=1
  ch=min(ch,num[i])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from math import factorial
p=10**9+7
n,k=map(int,input().split())
A=[int(i) for i in input().split()]
A.sort()

def nck(n,k):
  return factorial(n)//factorial(n-k)//factorial(k)

ans=0
if k==1:
  ans=0
else:
  for i in range(n):
    for j in range(k-1,n-i):
      ans+=(A[i+j]-A[i])*nck(j-1,k-2)
      ans=ans%p
print(ans)
      

Fixed submission:
n,k=map(int,input().split())
arr=[int(i) for i in input().split()]
arr.sort()

mod=10**9+7

#nCk
factorial=[1]
for i in range(1, n+1):
    factorial.append(factorial[-1] * i % mod)

inv_factorial = [-1] * (n+1)
inv_factorial[-1] = pow(factorial[-1], mod-2, mod)
for i in reversed(range(n)):
    inv_factorial[i] = inv_factorial[i+1] * (i+1) % mod

def fact(n):
    return factorial[n]

def nck(n, k):
    if k>n or k<0:
        return 0
    else:
        return factorial[n] * inv_factorial[n-k] * inv_factorial[k] %mod

m=0
for i in range(n):
  m%=mod
  m+=arr[i]*nck(n-i-1, k-1)


M=0
for i in range(n-1, -1, -1):
  M%=mod
  M+=arr[i]*nck(i, k-1)

print((M-m)%mod)
Buggy python submission (verdict: Time Limit Exceeded):
def main():
  n,m=map(int,input().split())
  happ=[-int(i) for i in input().split()]
  inf=10**6
  happ.sort()
  happ.append(inf)
  from heapq import heapify,heappop,heappush
  
  
  q=[[happ[0]+happ[0],0,0],[inf]]
  heapify(q)
  ans=0
  for _ in range(m):
    ma=heappop(q)
    while q[0]==ma:
      ma=heappop(q)
    ans+=-ma[0]
    i,j=ma[1],ma[2]
    heappush(q,[happ[i+1]+happ[j],i+1,j])
    heappush(q,[happ[i]+happ[j+1],i,j+1])
  print(ans)
if  __name__=='__main__':
  main()
    

Fixed submission:
def main():
    import numpy as np
    n,m=map(int,input().split())
    A=list(map(int,input().split()))
    A.sort()
    A=np.array(A)

    def cnt_shake(x): #握手の組であって合計パワーがx以上となる組みの数
        return n**2-np.searchsorted(A,x-A).sum()
  
    right=10**10*1
    left=-10**10-1
    while right-left>1:
        mid=(left+right)//2
        if cnt_shake(mid)<m:
            right=mid
        else:
            left=mid
    
    border=left  #border以上の握手をする
    C=n-np.searchsorted(A,border+1-A)
    B=np.cumsum(A[::-1])
    #print(border,A,B,C)

    s,cnt=0,0
    for i in range(n):
        if C[i]>0:
          cnt+=C[i]
          s+=B[C[i]-1]+A[i]*C[i]
    s+=border*(m-cnt)

    print(s)
if __name__=='__main__':
    main()
Buggy python submission (verdict: Runtime Error):
a=int(input())
b=int(input())

if a==1 and b==2:
  print(3)
elif a==1 and b==3:
  print(2)
elif a==2 and b==1:
  pirnt(3)
elif a==2 and b==3:
  print(1)
elif a==3 and b==1:
  print(2)
else:
  print(1)

Fixed submission:
a=int(input())
b=int(input())

if a==1 and b==2:
  print(3)
elif a==1 and b==3:
  print(2)
elif a==2 and b==1:
  print(3)
elif a==2 and b==3:
  print(1)
elif a==3 and b==1:
  print(2)
elif a==3 and b==2:
  print(1)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=[int(i) for i in input().split()]
  
if 1 not in A:
  ans=-1
else:
  ans=0
  for i in range(1,n+1):
    if i in A:
      k=A.index(i)
      ans+=k
      A=A[k+1:]
    else:
      ans+=len(A)
      break
print(ans)


Fixed submission:
n=int(input())
A=[int(i) for i in input().split()]

k=1
cnt=0
for i in range(n):
  if A[i]!=k:
    cnt+=1
  else:
    k+=1
if cnt==n:
  print(-1)
else:
  print(cnt)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
A=[int(i) for i in input().split()]
  
if 1 not in A:
  ans=-1
else:
  ans=0
  for i in range(1,n+1):
    if i in A:
      k=A.index(i)
      ans+=k
      A=A[k+1:]
    else:
      ans+=len(A)
      break
print(ans)

Fixed submission:
n=int(input())
A=[int(i) for i in input().split()]

k=1
cnt=0
for i in range(n):
  if A[i]!=k:
    cnt+=1
  else:
    k+=1
if cnt==n:
  print(-1)
else:
  print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(100000000)
input = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    H,W = map(int,input().split())
    A = [tuple(map(int,input().split())) for _ in range(H)]
    B = [tuple(map(int,input().split())) for _ in range(H)]

    dp = [[[0]*12800 for _ in range(W)] for _ in range(H)]
    dp[0][0][6400] = 1
    for i in range(H):
        for j in range(W):
            if i == H - 1 and j == W - 1:
                break
            a,b = A[i][j],B[i][j]
            for k in range(12800):
                if dp[i][j][k] == 0:
                    continue
                if 0 <= k + a - b < 12800:
                    if i + 1 < H:
                        dp[i + 1][j][k + a - b] |= dp[i][j][k]
                    if j + 1  < W:
                        dp[i][j + 1][k + a - b] |= dp[i][j][k]
                if 0 <= k - a + b < 12800:
                    if i + 1 < H:
                        dp[i + 1][j][k - a + b] |= dp[i][j][k]
                    if j + 1 < W:
                        dp[i][j + 1][k - a + b] |= dp[i][j][k]
    
    ans = INF
    a,b = A[-1][-1],B[-1][-1]
    for i in range(12800):
        if (0 <= i + a - b < 12800 and dp[-1][-1][i + a - b]) or (0 <= i - a + b < 12800 and dp[-1][-1][i - a + b]):
            ans = min(ans,abs(i - 6400))

    print(ans)                
if __name__ == '__main__':
    main()
    


Fixed submission:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    H,W = map(int,input().split())
    A = [list(map(int,input().split())) for _ in range(H)]
    B = [list(map(int,input().split())) for _ in range(H)]

    dp = [[0]*(1 + W) for _ in range(H + 1)]
    x = abs(A[0][0] - B[0][0])
    dp[0][0] = 1 << (12800 + x)
    dp[0][0] |= 1 << (12800 - x)
    for i in range(H):
        for j in range(W):
            c = abs(A[i][j] - B[i][j])
            if i > 0:
                dp[i][j] |= dp[i - 1][j] << c
                dp[i][j] |= dp[i - 1][j] >> c
            if j > 0:
                dp[i][j] |= dp[i][j - 1] << c
                dp[i][j] |= dp[i][j - 1] >> c
    ans = INF
    x = dp[H - 1][W - 1]
    for i in range(25600):
        if x&1:
            ans = min(ans,abs(i - 12800))
        x >>= 1
    print(ans)
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    from itertools import product
    n=int(input())
    s=input()
    
    cnt=0
    num='0123456789'
    for pw in product(num,repeat=3):
        j=0
        for i in range(n):
            if pw[j]==s[i]:
                j+=1
                if j==3:
                    cnt+=1
                    break
    
    print(cnt) 
if __name__=='__main__':
    main()

Fixed submission:
n=int(input())
s=input()

N=[str(i).zfill(3) for i in range(1000)]

cnt=0
for n in N:
  n0=s.find(n[0])
  if n0==-1:
    continue
  n1=s.find(n[1],n0+1)
  if n1==-1:
    continue
  n2=s.find(n[2],n1+1)
  if n2!=-1:
    cnt+=1
print(cnt)
Buggy python submission (verdict: Runtime Error):
def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    
    ans=[[0]*w for _ in range(h)]
    for idx in range(h):
        if '#' in s[idx]:
            i=idx
            break
            
    start,j,cnt,first,itigo=i,0,1,True,True
    while i<h:
        if s[i][j]=='#':
            if first:
                first=False
                itigo=False
                ans[i][j]=cnt
                j+=1
                continue
            cnt+=1
            ans[i][j]=cnt
        else:
            ans[i][j]=cnt

        j+=1
        if j==w:
            first=True
            if itigo:
                ans[i]=ans[i-1]
                i+=1
                j=0
                continue
            itigo=True
            i+=1
            j=0
            cnt+=1
    
    for i in range(start):
        ans[i]=ans[start]
    
    for i in range(h):
        print(*ans[i]) 
    
if __name__=='__main__':
    main()



Fixed submission:
def main():
    h,w,k=map(int,input().split())
    s=[list(input()) for _ in range(h)]
    
    ans=[[0]*w for _ in range(h)]
    for idx in range(h):
        if '#' in s[idx]:
            i=idx
            break
            
    start,j,cnt,first=i,0,1,True

    while i<h:
        if j==w:
            if first:
                ans[i]=ans[i-1]
                i+=1
                j=0
                continue
            first=True
            i+=1
            j=0
            cnt+=1
            continue

        if s[i][j]=='#':
            if first:
                first=False
                ans[i][j]=cnt
                j+=1
                continue
            cnt+=1
            ans[i][j]=cnt
        else:
            ans[i][j]=cnt

        j+=1
    
    for i in range(start):
        ans[i]=ans[start]
    
    for i in range(h):
        print(*ans[i]) 
    
if __name__=='__main__':
    main()
Buggy python submission (verdict: Runtime Error):
#n**p mod m を計算する(デフォルト引数は10**9+7)
def n_ruijyou_p(n,p,m=10**9+7):
    bin_p=format(p,'b')
    ans=1
    nruijyou2i=n
    
    if bin_p[0]=='1':
       ans=ans*nruijyou2i%m

    for i in range(1,len(bin_p)):
        nruijyou2i=(nruijyou2i)**2
        print(nruijyou2i)
        if bin_p[i]=='1':
            ans=ans*nruijyou2i%m
           
    return ans 
  
x,y=map(int,input().split())
print(n_ruijyou_p(x,y))

Fixed submission:
r=int(input())
print(r**2)

Buggy python submission (verdict: Runtime Error):
#互いに素なa,bについて、a*x+b*y=1の一つの解
def extgcd(a,b):
    r = [1,0,a]
    w = [0,1,b]
    while w[2]!=1:
        q = r[2]//w[2]
        r2 = w
        w2 = [r[0]-q*w[0],r[1]-q*w[1],r[2]-q*w[2]]
        r = r2
        w = w2
    #[x,y]
    return [w[0],w[1]]

# aの逆元(mod m)を求める。(aとmは互いに素であることが前提)
def mod_inv(a,m):
    if a%m!=0:
      x = extgcd(a,m)[0]
      return (m+x%m)%m
      

#nCk mod m を計算する(デフォルトの引数は10**9+7)
def c_mod(n,k,m=10**9+7):
  res = 1
  for i in range(1,n+1):
      if (i%m)!=0:
        res = res*i%m
      else:
        res=res/i%m
  for i in range(1,k+1):
      if (i%m)!=0:
        res = res*mod_inv(i,m)%m
      else:
        res=res/i%m
  for i in range(1,n-k+1):
      if (i%m)!=0:
        res = res*mod_inv(i,m)%m
      else:
        res=res/i%m
  return res


x,y=map(int,input().split())
if (2*x-y)%3==0 and (2*y-x)%3==0 and (2*y-x)>0 and (2*x-y)>0 :
  l=int((2*x-y)/3)
  k=int((2*y-x)/3)
  ans=c_mod(l+k,k)

else:
  ans=0
print(ans)


Fixed submission:
r=int(input())
print(r**2)
Buggy python submission (verdict: Runtime Error):
n=int(input())
ds=[int(i) for i in input().split()]
ans=0
counts={}

if ds[0]!=0:
  ans=0
  
else:  
    for i in range(1,n):
      if ds[i] not in counts:
        counts[ds[i]]=1
      else:
        counts[ds[i]]+=1
    ans=1
    for i in range(1,len(counts)):
      x=(counts[i]**counts[i+1])%998244353
      ans*=x
      ans%998244353

print(ans%998244353)
  

Fixed submission:
n=int(input())
ds=[int(i) for i in input().split()]
counts={}

if ds[0]!=0:
  ans=0

else:  
    for i in range(1,n):
      if ds[i] not in counts:
        counts[ds[i]]=1
      else:
        counts[ds[i]]+=1
    c=0
    for i in range(1,len(counts)+1):
      if i in counts:
        c+=1
    if c==len(counts):
      ans=1
      for i in range(1,len(counts)):
          x=(counts[i]**counts[i+1])%998244353
          ans*=x
          ans%998244353
    else:
      ans=0

print(ans%998244353)

Buggy python submission (verdict: Runtime Error):
n=int(input())
ds=[int(i) for i in input().split()]
ans=0
counts={}
if ds[0]!=0:
  ans=0
  
else:  
    for i in range(1,n):
      if ds[i] not in counts:
        counts[ds[i]]=1
      else:
        counts[ds[i]]+=1
    ans=1
    for i in range(1,len(counts)):
      ans*=counts[i]**counts[i+1]

print(ans)
  

Fixed submission:
n=int(input())
ds=[int(i) for i in input().split()]
counts={}

if ds[0]!=0:
  ans=0

else:  
    for i in range(1,n):
      if ds[i] not in counts:
        counts[ds[i]]=1
      else:
        counts[ds[i]]+=1
    c=0
    for i in range(1,len(counts)+1):
      if i in counts:
        c+=1
    if c==len(counts):
      ans=1
      for i in range(1,len(counts)):
          x=(counts[i]**counts[i+1])%998244353
          ans*=x
          ans%998244353
    else:
      ans=0

print(ans%998244353)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    prob = [tuple(map(int,input().split())) for _ in range(N)]
    
    #min_Rとmax_Lが同じグループにいる時
    max_L = 0
    min_R = INF
    cnt_max = 0 #L最大を満たすのが何個あるか
    cnt_min = 0 #R最小を満たすのが何個あるか
    for i,(l,r) in enumerate(prob):
        if l == max_L:
            cnt_max += 1
        elif l > max_L:
            cnt_max = 1
            max_L = l
        if r == min_R:
            cnt_min += 1
        elif r < min_R:
            cnt_min = 1
            min_R = r
    
    if cnt_min > 1 and cnt_max > 1:
        max_diff = max(r - l for l,r in prob)
    elif cnt_min > 1:
        max_diff = max(r - l for l,r in prob if l != max_L)
    elif cnt_max > 1:
        max_diff = max(r - l for l,r in prob if r != min_R)
    else:
        max_diff = max(r - l for l,r in prob if (r != min_R) and (l != max_L))
    
    ans1 = max_diff + max(min_R - max_L + 1,0) + 1
    
    #min_Rとmax_Lが違うグループにいる時
    prob.sort(key = lambda x:x[1])
    diff = prob[0][1] - prob[0][0]
    cummax_L = prob[0][0]
    for l,r in prob[1:]:
        diff = max(diff,r - cummax_L)
        cummax_L = max(cummax_L,l)
    
    ans2 = min_R - max_L + diff + 2

    print(max(ans1,ans2,0))
if __name__ == '__main__':
    main()

Fixed submission:
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

def main():
    N = int(input())
    prob = [tuple(map(int,input().split())) for _ in range(N)]
    
    if N == 2:
        ans = sum(r - l + 1 for l,r in prob)
        print(ans)
        return 

    #min_Rとmax_Lが同じグループにいる時
    max_L = 0
    min_R = INF
    cnt_max = 0 #L最大を満たすのが何個あるか
    cnt_min = 0 #R最小を満たすのが何個あるか
    for l,r in prob:
        if l == max_L:
            cnt_max += 1
        elif l > max_L:
            cnt_max = 1
            max_L = l
        if r == min_R:
            cnt_min += 1
        elif r < min_R:
            cnt_min = 1
            min_R = r
    
    if cnt_min > 1 and cnt_max > 1:
        max_diff = max(r - l for l,r in prob) + 1
    elif cnt_min > 1:
        max_diff = max(r - l for l,r in prob if l != max_L) + 1
    elif cnt_max > 1:
        max_diff = max(r - l for l,r in prob if r != min_R) + 1
    else:
        max_diff = max(r - l for l,r in prob if (r != min_R) and (l != max_L)) + 1
    
    ans1 = max_diff + max(min_R - max_L + 1,0)
    
    #min_Rとmax_Lが違うグループにいる時
    prob.sort(key = lambda x:(x[1],x[0]))
    cummax_L = prob[0][0]
    ans2 = 0
    for l,r in prob[1:]:
        ans2 = max(ans2,max(r - max_L + 1,0) + max(min_R - cummax_L + 1,0))
        cummax_L = max(cummax_L,l)

    print(max(ans1,ans2))
if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
import math
list=[ ]

for i in range(1,math.floor(n*0.5)+1):
  if (n/i)%1==0:
    j=n/i
    list.append(i+j)

print(int(min(list)-2))


Fixed submission:
n=int(input())
import math
list=[ ]

for i in range(1,math.floor(n**0.5)+1):
  if (n/i)%1==0:
    j=n/i
    list.append(i+j)

print(int(min(list)-2))

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
import math
list=[ ]

for i in range(1,math.floor(n*0.5)+1):
  if float(n/i).is_integer()==True:
    j=n/i
    list.append(i+j)

print(int(min(list)-2))

Fixed submission:
n=int(input())
import math
list=[ ]

for i in range(1,math.floor(n**0.5)+1):
  if (n/i)%1==0:
    j=n/i
    list.append(i+j)

print(int(min(list)-2))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
L=[int(i) for i in input().split()]
L.sort(reverse=True)

def binary(a,b,mid):
  if  L[mid]+L[j]>L[i]:
    return True
  else:
    return False

ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    l=j
    r=n
    while r-l>1:
      mid=(r+l)//2
      if binary(i,j,mid):
        l=mid
      else:
        r=mid
    ans+=l-j
print(ans)
        

Fixed submission:
from bisect import bisect_right
n=int(input())
L=[int(i) for i in input().split()]
L.sort()


ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    c=L[i]+L[j]-1
    ans+=bisect_right(L,c)-j-1
    
print(ans)

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

n=int(input())
L=[int(i) for i in input().split()]
L.sort()

ans=0
for i in range(2,n):
  c=list(itertools.combinations(L[:i],2))
  for j in range(len(c)):
     if  math.floor(c[j][0]-c[j][1])<L[i]<c[j][0]+c[j][1]:
        ans+=1
print(ans)

Fixed submission:
from bisect import bisect_right
n=int(input())
L=[int(i) for i in input().split()]
L.sort()


ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    c=L[i]+L[j]-1
    ans+=bisect_right(L,c)-j-1
    
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
lengths=sorted([int(i) for i in input().split()])
import itertools as it
import math as ma

cnt=0
triangle=[list(i) for i in it.combinations(lengths,3)]

for i in range(len(triangle)):
    a=triangle[i].pop(0)
    b=triangle[i].pop(0)
    c=triangle[i].pop(0)
    if  ma.floor(b-a)<c<(b+a):
        cnt+=1

print(cnt)

Fixed submission:
from bisect import bisect_right
n=int(input())
L=[int(i) for i in input().split()]
L.sort()


ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    c=L[i]+L[j]-1
    ans+=bisect_right(L,c)-j-1
    
print(ans)