Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
a,b,k=map(int,input().split())
S=[]
for i in range(a,b+1):
    S.append(i)
T=sorted(list(set(S[:k]+S[-k:])))
for i in T:
    print(i)

Fixed submission:
a,b,k=map(int,input().split())
S=[]

for i in range(k):
    if a+i>b:
        break
    S.append(a+i)
    
for i in range(k):
    if b-i<a:
        break
    S.append(b-i)
    
S=sorted(list(set(S)))
for i in S:
    print(i)

Buggy python submission (verdict: Time Limit Exceeded):
a,b,k=map(int,input().split())
S=[]
for i in range(a,b+1):
    S.append(i)
T=sorted(list(set(S[:k]+S[-k:])))

for i in T:
    print(i)

Fixed submission:
a,b,k=map(int,input().split())
S=[]

for i in range(k):
    if a+i>b:
        break
    S.append(a+i)
    
for i in range(k):
    if b-i<a:
        break
    S.append(b-i)
    
S=sorted(list(set(S)))
for i in S:
    print(i)
Buggy python submission (verdict: Runtime Error):
N=int(input())
M,A,R,C,H=0,0,0,0,0
for i in range(N):
    s=input()[0]
    if s=='M':
        M+=1
    elif s=='A':
        A+=1
    elif s=='R':
        R+=1
    elif s=='C':
        C+=1
    elif s=='H':
        H+=1

print(M*A*R + M*A*C + M*A*H + M*R*C + M*R*H + \
      M*C*H + A*R*C + A*R*H + A*C*H + R*C*H)

Fixed submission:
print(int(input())//3)
Buggy python submission (verdict: Runtime Error):
from collections import deque

H,W=map(int,input().split())
c=[['#']*(W+2)]
ten=0
for i in range(H):
    ip=list(input())
    ten+=ip.count('.')
    c.append(['#']+ip+['#'])
c.append(['#']*(W+2))
Q=deque([[1,1,1]])

def move(yxc):
    global Q,c
    y,x,cost=yxc[0],yxc[1],yxc[2]
    if c[y+1][x]=='.':
        c[y+1][x]=cost+1
        Q.append([y+1,x,cost+1])
    if c[y-1][x]=='.':
        c[y-1][x]=cost+1
        Q.append([y-1,x,cost+1])
    if c[y][x+1]=='.':
        c[y][x+1]=cost+1
        Q.append([y,x+1,cost+1])
    if c[y][x-1]=='.':
        c[y][x-1]=cost+1
        Q.append([y,x-1,cost+1])

c[1][1]=1
while len(Q)>0:
    move(Q.popleft())

goal=c[H][W]
print(ten-goal)

Fixed submission:
from collections import deque

H,W=map(int,input().split())
c=[['#']*(W+2)]
ten=0
for i in range(H):
    ip=list(input())
    ten+=ip.count('.')
    c.append(['#']+ip+['#'])
c.append(['#']*(W+2))
Q=deque([[1,1,1]])

def move(yxc):
    global Q,c
    y,x,cost=yxc[0],yxc[1],yxc[2]
    if c[y+1][x]=='.':
        c[y+1][x]=cost+1
        Q.append([y+1,x,cost+1])
    if c[y-1][x]=='.':
        c[y-1][x]=cost+1
        Q.append([y-1,x,cost+1])
    if c[y][x+1]=='.':
        c[y][x+1]=cost+1
        Q.append([y,x+1,cost+1])
    if c[y][x-1]=='.':
        c[y][x-1]=cost+1
        Q.append([y,x-1,cost+1])

c[1][1]=1
while len(Q)>0:
    move(Q.popleft())

goal=c[H][W]
if goal=='.' or goal=='#':
    print(-1)
else:
    print(ten-goal)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
TXY=[list(map(int,input().split())) for i in range(N)]

Next=TXY.pop(0)
Flag=1

for i in range(N):
#    print(Next)
    D=Next[0]-abs(Next[1])-abs(Next[2])
    if D<0 or D%2!=0:
        Flag=0
        break
    else:
        if TXY==[]:
            break
        else:
            Next2=TXY.pop(0)
            Next=[Next2[0]-Next[0],Next2[1]-Next[1],Next2[2]-Next[2]]

print(['No','Yes'][Flag])

Fixed submission:
N=int(input())
TXY=[list(map(int,input().split())) for i in range(N)]

Next=TXY.pop(0)
Flag=1

for i in range(N):
    D=Next[0]-abs(Next[1])-abs(Next[2])
    if D<0 or D%2!=0:
        Flag=0
        break
    else:
        if TXY==[]:
            break
        else:
            Next2=TXY.pop(0)
            Next=[Next2[0]-Next[0],Next2[1]-Next[1],Next2[2]-Next[2]]

print(['No','Yes'][Flag])
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
A.sort();B.sort();C.sort()
AB=[0 for i in range(N)]
BC=[0 for i in range(N)]

def find_gt(a,x):
    i = bisect.bisect_right(a,x)
    if i != len(a):
        return N-i
    else:
        return 0

for i in range(N):
    AB[i]=find_gt(B,A[i])
    BC[i]=find_gt(C,B[i])

ans=0
for i in range(N):
    ans+=sum(BC[N-AB[i]:])
print(ans)

Fixed submission:
import bisect

N=int(input())
A=sorted(list(map(int,input().split())))
B=sorted(list(map(int,input().split())))
C=sorted(list(map(int,input().split())))
ans=0

for i in range(N):
    a=bisect.bisect_left(A,B[i])
    c=N-bisect.bisect_right(C,B[i])
    ans+=a*c

print(ans)
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]


def UF_make(Graph):
    ret=[-1]*(N+1)
    for i in range(len(Graph)):
        v1=[ret[Graph[i][0]],Graph[i][0]][ret[Graph[i][0]]<0]
        v2=[ret[Graph[i][1]],Graph[i][1]][ret[Graph[i][1]]<0]
        if v1!=v2:
            if ret[v1]>ret[v2]:
                v1,v2=v2,v1
            ret[v1]+=ret[v2]
            ret[v2]=v1
    return ret

def UF_check(Array,V1,V2):
    v1=[Array[V1],V1][Array[V1]<0]
    v2=[Array[V2],V2][Array[V2]<0]
    return(True if v1==v2 else False)

def UF(Graph,V1,V2):
    return(UF_check(UF_make(Graph),V1,V2))

ans=0
for i in range(M):
    if UF(AB[:i]+AB[i+1:],AB[i][0],AB[i][1])==False:
        ans+=1

print(ans)

Fixed submission:
N,M=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(M)]

def find_root(root,x):
    y = root[x]
    if x == y:
        return x
    z = find_root(root,y)
    root[x] = z
    return z
 
def merge(root,size,x,y):
    x = find_root(root,x)
    y = find_root(root,y)
    if x == y:
        return
    sx,sy = size[x],size[y]
    if sx < sy:
        sx,sy = sy,sx
        x,y = y,x
    root[y] = x
    size[x] += sy

def UF_make(graph,n):
    Root=list(range(n+1))
    Size=[1] * (n+1)
    for i in range(len(graph)):
        merge(Root,Size,graph[i][0],graph[i][1])
    for i in range(n+1):
        Root[i] = find_root(Root,i)
    Root.pop(0)  #
    return Root

ans=0
for i in range(M):
    if len(set((UF_make(AB[:i]+AB[i+1:],N))))!=1:
        ans+=1

print(ans)
Buggy python submission (verdict: Runtime Error):
A,B,C,D,E,F=map(int,input().split())

water=[]
for i in range(31):
    for j in range(30):
        if (A*i+B*j)*100<=F:
            water.append((A*i+B*j)*100)
sugar=[]
for i in range(501):
    for j in range(500):
        if C*i+D*j<=F//2:
            sugar.append(C*i+D*j)

ans_sum=A*100
ans_sugar=0
ans_rate=0
for i in water:
    for j in sugar:
        if i==0:
            continue
        if i+j<=F and ans_rate<j/i<=E/100:
            ans_sum=i+j
            ans_sugar=j
            ans_rate=j/i

print(ans_sum,ans_sugar)

Fixed submission:
n,a=map(int,open(0));print(n**2-a)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(input()) for i in range(N)]
S=list(set(A))

ans=0
for i in S:
    if A.count(i)%2==1:
        ans+=1

print(ans)

Fixed submission:
N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
c=1
ans=0

for i in range(1,N):
    if A[i]!=A[i-1]:
        if c%2==1:
            ans+=1
        c=1
    else:
        c+=1

if c%2==1:
    ans+=1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(input()) for i in range(N)]
S=list(set(A))

ans=0
for i in S:
    if A.count(i)%2==1:
        ans+=1

print(ans)

Fixed submission:
N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
c=1
ans=0

for i in range(1,N):
    if A[i]!=A[i-1]:
        if c%2==1:
            ans+=1
        c=1
    else:
        c+=1

if c%2==1:
    ans+=1

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=[int(input()) for i in range(N)]
S=list(set(A))
C=[0]*len(S)

for i in range(N):
    C[S.index(A[i])]+=1

ans=0
for i in C:
    if i%2==1:
        ans+=1

print(ans)

Fixed submission:
N=int(input())
A=[int(input()) for i in range(N)]
A.sort()
c=1
ans=0

for i in range(1,N):
    if A[i]!=A[i-1]:
        if c%2==1:
            ans+=1
        c=1
    else:
        c+=1

if c%2==1:
    ans+=1

print(ans)
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=sorted(list(map(int,input().split())))
C=[0]*(max(A)+1)

for i in A:
    C[i]+=1

if len(C)==0:
    print(C[0])
else:
    T=max(C[0]+C[1],C[-1]+C[-2])
    for i in range(1,max(A)):
        T=max(T,C[i-1]+C[i]+C[i+1])
    print(T)

Fixed submission:
N=int(input())
A=sorted(list(map(int,input().split())))
C=[0]*(max(A)+1)

for i in A:
    C[i]+=1

if len(C)==1:
    print(C[0])
else:
    T=max(C[0]+C[1],C[-1]+C[-2])
    for i in range(1,max(A)):
        T=max(T,C[i-1]+C[i]+C[i+1])
    print(T)

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=sorted(list(map(int,input().split())))
C=[0]*(max(A)+1)

for i in A:
    C[i]+=1

T=max(C[0]+C[1],C[-1]+C[-2])
for i in range(1,max(A)):
    T=max(T,C[i-1]+C[i]+C[i+1])

print(T)

Fixed submission:
N=int(input())
A=sorted(list(map(int,input().split())))
C=[0]*(max(A)+1)

for i in A:
    C[i]+=1

if len(C)==1:
    print(C[0])
else:
    T=max(C[0]+C[1],C[-1]+C[-2])
    for i in range(1,max(A)):
        T=max(T,C[i-1]+C[i]+C[i+1])
    print(T)
Buggy python submission (verdict: Runtime Error):
N=int(input())
P=list(map(int,input().split()))

c=[]
for i in range(N):
    if P[i]==i+1:
        c.append(i+1)

import sys
if c==[]:
    print(0)
    sys.exit()

d=[]
for i in range(1,len(c)):
    d.append(c[i]-c[i-1])

if len(c)==2:
    print(c[1]-c[0])
elif len(c)%2==0:
    print(sum(d)-max(d))
else:
    print(sum(d)-max(d)+1)

Fixed submission:
N=int(input())
P=list(map(int,input().split()))
Q=P[::-1]
c=0
for i in range(N-1):
    if P[i]==i+1:
        P[i],P[i+1]=P[i+1],P[i]
        c+=1
if P[N-1]==N:
    c+=1
print(c)
Buggy python submission (verdict: Runtime Error):
n,m=map(int,open(0));print((n-1)*(m-1))

Fixed submission:
n,m=map(int,input().split());print((n-1)*(m-1))
Buggy python submission (verdict: Runtime Error):
N=int(input())
A=sorted(list(map(int,input().split())))
A=[i//400 for i in A]

Colors=[0,0,0,0,0,0,0,0,0]
for i in A:
    Colors[i]+=1

Count=0
for i in range(8):
    if Colors[i]>0:
        Count+=1
if Count==0:
    Count=1

print(Count,Count+Colors[-1])

Fixed submission:
N=int(input())
A=sorted(list(map(int,input().split())))
A=[i//400 for i in A]

Colors=[0,0,0,0,0,0,0,0,0]
for i in A:
    if i>=8:
        Colors[8]+=1
    else:
        Colors[i]+=1

Count=0
for i in range(8):
    if Colors[i]>0:
        Count+=1

print(max(Count,1),Count+Colors[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
A.sort()
S=[]
D=[]

for i in A:
    if i in S:
        D.append(i)
    else:
        S.append(i)
S=set(S)

import sys
if D==[]:
    print(N)
    sys.exit()

M=N-len(D)
if len(D)%2==1:
    print(M-1)
else:
    MaxD,MinD=D[-1],D[0]
    Med=-1
    for i in S:
        if MinD<=i<=MaxD:
            Med=i
            print(M)
            break
    if Med==-1:
        print(M-2)

Fixed submission:
N=int(input());A=list(map(int,input().split()));S=len(set(A));print(S-1+S%2)

Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
S=[]
D=[]

for i in A:
    if i in S:
        D.append(i)
    else:
        S.append(i)

import sys
if D==[]:
    print(N)
    sys.exit()

M=N-len(D)
if len(D)%2==1:
    print(M-1)
else:
    MaxD,MinD=max(D),min(D)
    Med=-1
    for i in S:
        if MinD<=i<=MaxD:
            Med=i
            print(M)
            break
    if Med==-1:
        print(M-2)

Fixed submission:
N=int(input());A=list(map(int,input().split()));S=len(set(A));print(S-1+S%2)

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))
A.sort()
S=[]
D=[]

for i in A:
    if i in S:
        D.append(i)
    else:
        S.append(i)
#print(D)
M=N-len(D)

if len(D)%2==1:
    print(M-1)
else:
    MaxD,MinD=max(D),min(D)
    Med=-1
    for i in S:
        if MinD<=i<=MaxD:
            Med=i
            print(M)
            break
    if Med==-1:
        print(M-2)

Fixed submission:
N=int(input());A=list(map(int,input().split()));S=len(set(A));print(S-1+S%2)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
TA=[list(map(int,input().split())) for i in range(N)]
Taka=1
Aoki=1

def UP(V1,V2,R1,R2):
    r1,r2=R1,R2
    while V1>R1 or V2>R2:
        R1+=r1
        R2+=r2
    return [R1,R2]

for i in range(N):
    up=UP(Taka,Aoki,TA[i][0],TA[i][1])
    Taka=up[0]
    Aoki=up[1]

print(Taka+Aoki)

Fixed submission:
N=int(input())
TA=[list(map(int,input().split())) for i in range(N)]
Taka=1
Aoki=1

def UP(V1,V2,R1,R2):
    n=max(-(-V1//R1),-(-V2//R2))
    return(n*R1,n*R2)

for i in range(N):
    up=UP(Taka,Aoki,TA[i][0],TA[i][1])
#    print(up)
    Taka=up[0]
    Aoki=up[1]

print(Taka+Aoki)
Buggy python submission (verdict: Runtime Error):
s=int(input())
mod=10**9+7


dp=[1]*(s+1)

dp[0]=0
dp[1]=0
dp[2]=0


#print(dp)
for i in range(3,s+1):
    for j in range(3,s-i+1):
        dp[i+j]+=dp[i]%mod
    #print(i,dp)
print(dp[s]%mod)







Fixed submission:
s=int(input())
mod=10**9+7

if s<3:
    print(0)
    exit()

dp=[1]*(s+1)

dp[0]=0
dp[1]=0
dp[2]=0

#print(dp)
for i in range(3,s+1):
    for j in range(3,s-i+1):
        dp[i+j]+=dp[i]%mod
    #print(i,dp)
print(dp[s]%mod)

Buggy python submission (verdict: Time Limit Exceeded):
s=int(input())
mod=10**9+7


dp=[[0]*(s+1) for _ in range(s)]

for i in range(3,s+1):
    dp[0][i]=1

ans=0
ans+=dp[0][s]

for keta in range(1,s//3+1):
    #print("keta",keta)
    for ss in range(3*keta,s-2):
        for k in range(3,s+1):
            if ss+k<=s:
                dp[keta][ss+k]+=dp[keta-1][ss]%mod
            else:
                break

    ans+=dp[keta][s]%mod

#print(dp)
    

print(ans%mod)






Fixed submission:
s=int(input())
mod=10**9+7

if s<3:
    print(0)
    exit()

dp=[1]*(s+1)

dp[0]=0
dp[1]=0
dp[2]=0

#print(dp)
for i in range(3,s+1):
    for j in range(3,s-i+1):
        dp[i+j]+=dp[i]%mod
    #print(i,dp)
print(dp[s]%mod)

Buggy python submission (verdict: Time Limit Exceeded):
s=int(input())
mod=10**9+7


dp=[[0]*(s+1) for _ in range(s)]

for i in range(3,s+1):
    dp[0][i]=1

ans=0
ans+=dp[0][s]

for keta in range(1,s//3+1):
    #print("keta",keta)
    flag=0
    for ss in range(3*keta,s+1):
        for k in range(3,s+1):

            if ss+k<=s:
                dp[keta][ss+k]+=dp[keta-1][ss]
                dp[keta][ss+k]%=mod
            else:
                break


    ans+=dp[keta][s]
    ans%=mod

#print(dp)
    

print(ans%mod)






Fixed submission:
s=int(input())
mod=10**9+7

if s<3:
    print(0)
    exit()

dp=[1]*(s+1)

dp[0]=0
dp[1]=0
dp[2]=0

#print(dp)
for i in range(3,s+1):
    for j in range(3,s-i+1):
        dp[i+j]+=dp[i]%mod
    #print(i,dp)
print(dp[s]%mod)

Buggy python submission (verdict: Time Limit Exceeded):
s=int(input())
mod=10**9+7


dp=[[0]*(s+1) for _ in range(s)]

for i in range(3,s+1):
    dp[0][i]=1

ans=0
ans+=dp[0][s]

for keta in range(1,s//3+1):
    #print("keta",keta)
    flag=0
    for ss in range(3*keta,s+1):
        for k in range(3,s+1):

            if ss+k<=s:
                dp[keta][ss+k]+=dp[keta-1][ss]
                dp[keta][ss+k]%=mod


    ans+=dp[keta][s]
    ans%=mod

#print(dp)
    

print(ans%mod)






Fixed submission:
s=int(input())
mod=10**9+7

if s<3:
    print(0)
    exit()

dp=[1]*(s+1)

dp[0]=0
dp[1]=0
dp[2]=0

#print(dp)
for i in range(3,s+1):
    for j in range(3,s-i+1):
        dp[i+j]+=dp[i]%mod
    #print(i,dp)
print(dp[s]%mod)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7
ans=0
for i in range(n-1):
    for j in range(i+1,n):
        ans+=(a[i]*a[j])%mod
        ans=ans%mod

print(ans%mod)



Fixed submission:
n=int(input())
a=list(map(int,input().split()))
mod=10**9+7

tmp=a[-1]
ans=0
for i in range(n-1):
    ii=n-i-2
    #print(ii)
    ans+=(tmp*a[ii])%mod
    ans=ans%mod
    tmp+=a[ii]%mod

print(ans%mod)
Buggy python submission (verdict: Time Limit Exceeded):
r,c,k=map(int,input().split())

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

rck=[[0]*c for _ in range(r)]

for [rr,cc,kk] in fuck:
    rck[rr-1][cc-1]=kk

#dp[y][x][cnt]

dp=[[[0]*4 for _ in range(c)] for _ in range(r)]
#print(dp)
for y in range(r):
    for x in range(c):
        #1行目
        if y == 0:
            if x==0:
                dp[y][x][1]=rck[y][x]
            if x>=1:
                dp[y][x][1]=max(dp[y][x-1][1],rck[y][x])
                dp[y][x][2]=max(dp[y][x-1][2],dp[y][x-1][1]+rck[y][x])
            if x>=2:
                dp[y][x][3]=max(dp[y][x-1][3],dp[y][x-1][2]+rck[y][x])
        else:
            #1は、上0+1 or 左0+1 or 上1 or 左1
            #count1ケース
            for i in range(1,4):
                if i==1:
                    uemax=max([max(dp[y-1][x][1],dp[y-1][x][2],dp[y-1][x][3])])
                    dp[y][x][i]=uemax+rck[y][x]
                    if x>0:
                        dp[y][x][i]=max(dp[y][x][i],dp[y][x-1][i])
                elif i>=2:
                    if x>=1:
                        dp[y][x][i]=max(dp[y][x-1][i],dp[y][x-1][i-1]+rck[y][x])

print(max(dp[-1][-1]))
             
             

Fixed submission:
def pri(x):
    for item in x:
        print(item)

r,c,k=map(int,input().split())

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

rck=[[0]*(c+1) for _ in range(r+1)]

for [rr,cc,kk] in fuck:
    rck[rr][cc]=kk
#pri(rck)
#dp[y][x][cnt]

dp=[[0]*4 for _ in range(c+1)]
#print(dp)
for y in range(1,r+1):
    for x in range(1,c+1):
        
        dp[x][0]=max(dp[x-1][0],dp[x][0],dp[x][1],dp[x][2],dp[x][3])
        dp[x][1]=max(dp[x][0]+rck[y][x],dp[x][1],dp[x-1][1])
        dp[x][2]=max(dp[x-1][1]+rck[y][x],dp[x][2],dp[x-1][2],dp[x][1])
        dp[x][3]=max(dp[x-1][2]+rck[y][x],dp[x][3],dp[x-1][3],dp[x][2])
        #print(y,x,dp)

print(max(dp[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))

ll=0
rr=10**9+1
for _ in range(10**3):
  #最も長い丸太がこれになる
  ans=(ll+rr)/2.0
  cnt=0
  for item in a:
    if item>ans:
	    cnt+=((-1*item)//ans)*(-1)-1
  if cnt<=k:
    rr=ans
  else:
    ll=ans
print(int((-1*ans//1)*(-1)))

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))

ll=0
rr=10**9+1
for _ in range(10**2):
  #最も長い丸太がこれになる
  ans=(ll+rr)/2.0
  cnt=0
  for item in a:
    if item>ans:
	    cnt+=((-1*item)//ans)*(-1)-1
  if cnt<=k:
    rr=ans
  else:
    ll=ans
print(int((-1*ans//1)*(-1)))

Buggy python submission (verdict: Time Limit Exceeded):
n,k=map(int,input().split())
a=list(map(int,input().split()))

ll=0
rr=10**9+1
for _ in range(10**5):
  #最も長い丸太がこれになる
  ans=(ll+rr)/2.0
  cnt=0
  for item in a:
    if item>ans:
	    cnt+=((-1*item)//ans)*(-1)-1
  if cnt<=k:
    rr=ans
  else:
    ll=ans
print(int((-1*ans//1)*(-1)))

Fixed submission:
n,k=map(int,input().split())
a=list(map(int,input().split()))

ll=0
rr=10**9+1
for _ in range(10**2):
  #最も長い丸太がこれになる
  ans=(ll+rr)/2.0
  cnt=0
  for item in a:
    if item>ans:
	    cnt+=((-1*item)//ans)*(-1)-1
  if cnt<=k:
    rr=ans
  else:
    ll=ans
print(int((-1*ans//1)*(-1)))
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())

tree=[[] for _ in range(n)]

for _ in range(n-1):
    u,v=map(int,input().split())
    tree[u-1].append(v-1)
    tree[v-1].append(u-1)

ans=0

for l in range(n):

    num_hen=0
    for r in range(l,n):
        
        for item in tree[r]:
            if item>=l and r>=item:
                num_hen+=1
        #print(l+1,r+1,(r-l+1)-num_hen)
        ans+=((r-l+1)-num_hen)

print(ans)




Fixed submission:
n=int(input())

num_chouten=0

for i in range(n):
    num_chouten+=((i+1)*(n-i))

num_hen=0
for _ in range(n-1):
    u,v=map(int,input().split())

    minnum=min(u,v)
    maxnum=max(u,v)

    num_hen+=minnum*(n-maxnum+1)

print(num_chouten-num_hen)
Buggy python submission (verdict: Time Limit Exceeded):
n=int(input())

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

ans=0
for i in range(1,n+1):
    ans+=i*len(make_divisors(i))


print(ans)


        




    






Fixed submission:
n=int(input())

yakusu=[0]*(n+1)

for i in range(1,n+1):
    for j in range(1,n+1):
        if i*j<=n:
            yakusu[i*j]+=1
        else:
            break

ans=0
for i,v in enumerate(yakusu):
    ans+=i*v

print(ans)

Buggy python submission (verdict: Runtime Error):
n=int(input())

import sympy

ans=0
for i in range(1,n+1):
    ans+=i*sympy.divisors(i)


print(ans)


        




    






Fixed submission:
n=int(input())

yakusu=[0]*(n+1)

for i in range(1,n+1):
    for j in range(1,n+1):
        if i*j<=n:
            yakusu[i*j]+=1
        else:
            break

ans=0
for i,v in enumerate(yakusu):
    ans+=i*v

print(ans)
Buggy python submission (verdict: Runtime Error):
#鬼
a,v=map(int,input().split())

#逃げている
b,w=map(int,input().split())

#t秒以内
t=int(input())

if v>w:
    abs(a-b)>=v*w*t:
    print("YES")
    exit()
else:
    print("NO")

Fixed submission:
#鬼
a,v=map(int,input().split())

#逃げている
b,w=map(int,input().split())

#t秒以内
t=int(input())

if v>w:
    if abs(a-b)<=(v-w)*t:
        print("YES")
        exit()

print("NO")
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))


if n==0:
    if a[0]==1:
        print(1)
    else:
        print(-1)
    exit()

if a[0]==1 and n!=0:
    print(-1)
    exit()

suma=sum(a)
node=1
cnt=0
for i,aa in enumerate(a[::-1]):
    cnt+=min(cnt+aa,2**(i-1))

print(cnt)
    
        


                    
        


    
print(cnt)

    
    
    





Fixed submission:
n=int(input())
a=list(map(int,input().split()))


if n==0:
    if a[0]==1:
        print(1)
    else:
        print(-1)
    exit()

if a[0]==1 and n!=0:
    print(-1)
    exit()

suma=sum(a)

cnt=1
bk=1

for i,aa in enumerate(a[1:]):
    node=min(suma,bk*2)
    cnt+=node
    #print(i,aa,node)
    bk=node-aa
    suma-=aa

if bk==0:
    print(cnt)
else:
    print(-1)
Buggy python submission (verdict: Runtime Error):
n=int(input())
a=list(map(int,input().split()))

tree=[[] for _ in range(n)]
for _ in range(n-1):
    aa,bb=map(int,input().split())
    tree[aa-1].append(bb-1)
    tree[bb-1].append(aa-1)

ans=[0]*n
import bisect

#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

def lisOnTree(x,lis):
    global ans,tree,a,n
    i=bisect.bisect_left(lis, a[x])
    if i==len(lis):
        lis.append(a[x])
        flag="append"
    else:
        flag=(i,lis[i])
        lis[i]=a[x]
    #print(x,lis)
    ans[x]=len(lis)
    for item in tree[x]:
        if ans[item]==0:
            lisOnTree(item,lis)
    if flag=="append":
        lis.pop()
    else:
        lis[flag[0]]=flag[1]

lisOnTree(0,[])

for item in ans:
    print(item)


    




Fixed submission:
import sys
sys.setrecursionlimit(2147483647)

n=int(input())
a=list(map(int,input().split()))

tree=[[] for _ in range(n)]
for _ in range(n-1):
    aa,bb=map(int,input().split())
    tree[aa-1].append(bb-1)
    tree[bb-1].append(aa-1)

ans=[0]*n
import bisect

#bisect.bisect_left(a, 4) #被ったら左側のindexを返す
#bisect.bisect_right(a, 4)#被ったら右側のindexを返す

def lisOnTree(x,lis):
    global ans,tree,a,n
    i=bisect.bisect_left(lis, a[x])
    if i==len(lis):
        lis.append(a[x])
        flag="append"
    else:
        flag=(i,lis[i])
        lis[i]=a[x]
    #print(x,lis)
    ans[x]=len(lis)
    for item in tree[x]:
        if ans[item]==0:
            lisOnTree(item,lis)
    if flag=="append":
        lis.pop()
    else:
        lis[flag[0]]=flag[1]

lisOnTree(0,[])

for item in ans:
    print(item)