Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
A = list(map(int,input().split()))

import numpy as np

def gcd(x, y):
    while x != 0 and y != 0:
        x, y = max(x, y), min(x, y)
        x %= y
    return y

def lcm(x,y):
    return x*y//gcd(x,y)

a = 0
for i in range(n):
    if A[i]%2==1:
        a = 1
if a==1:
    print(0)
else:
    for i in range(n):
        A[i] //= 2
    b = A[0]
    for i in range(1,n):
        b = np.lcm(A[i],b)
    # print(b)

    # b=np.lcm.reduce(A)

    ans = m//(b*2)
    if (m//(b*2))*(b*2)+b<=m:
        ans += 1
    print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
A = list(map(int,input().split()))

# import numpy as np

# def gcd(x, y):
#     while x != 0 and y != 0:
#         x, y = max(x, y), min(x, y)
#         x %= y
#     return y

from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

import sys

a = 0

B = [0] * n
C = A[:]

for i in range(n):
    while A[i] % 2 == 0:
        A[i] //= 2
        B[i] += 1

if len(set(B)) != 1:
    print("0")
else:
    for i in range(n):
        C[i] //= 2
    A = C
    b = A[0]
    for i in range(1,n):
        b = lcm(A[i], b)
        if b > m:
            print(0)
            sys.exit()
        # b = np.lcm(A[i],b)
    # print("b", b)

    # b=np.lcm.reduce(A)

    ans = (m//b + 1) // 2
    # if (m//(b*2))*(b*2)+b<=m:
    #     ans += 1
    print(ans)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
A = list(map(int,input().split()))

import numpy as np

def gcd(x, y):
    while x != 0 and y != 0:
        x, y = max(x, y), min(x, y)
        x %= y
    return y

def lcm(x,y):
    return x*y//gcd(x,y)

a = 0
for i in range(n):
    if A[i]%2==1:
        a = 1
if a==1:
    print(0)
else:
    for i in range(n):
        A[i] //= 2
    # b = A[0]
    # for i in range(1,n):
    #     b = lcm(b,A[i])
    # print(b)

    b=np.lcm.reduce(A)

    ans = m//(b*2)
    if (m//(b*2))*(b*2)+b<=m:
        ans += 1
    print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
n,m = map(int,input().split())
A = list(map(int,input().split()))

# import numpy as np

# def gcd(x, y):
#     while x != 0 and y != 0:
#         x, y = max(x, y), min(x, y)
#         x %= y
#     return y

from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

import sys

a = 0

B = [0] * n
C = A[:]

for i in range(n):
    while A[i] % 2 == 0:
        A[i] //= 2
        B[i] += 1

if len(set(B)) != 1:
    print("0")
else:
    for i in range(n):
        C[i] //= 2
    A = C
    b = A[0]
    for i in range(1,n):
        b = lcm(A[i], b)
        if b > m:
            print(0)
            sys.exit()
        # b = np.lcm(A[i],b)
    # print("b", b)

    # b=np.lcm.reduce(A)

    ans = (m//b + 1) // 2
    # if (m//(b*2))*(b*2)+b<=m:
    #     ans += 1
    print(ans)
Buggy python submission (verdict: Runtime Error):
t1,t2 = map(int,input().split())

a1,a2 = map(int,input().split())
b1,b2 = map(int,input().split())
c1 = b1-a1
c2 = b2-a2

s = t1*c1
t = s + t2*c2
print(c1,c2,s,t)
ans = -1
if s * t > 0:
    ans = 0
elif t == 0:
    ans="infinity"
else:
    if s > t:
        tt = abs(t)
        ans = -((-s / tt)//1)*2 - 1
        if s / tt - s//tt < 10**-25:
            ans += 1
    else:
        ss = abs(s)
        ans = -((-ss / t)//1)*2 - 1
        if ss / t -ss//t < 10**-25:
            ans += 1
print(int(ans))

Fixed submission:
t1,t2 = map(int,input().split())

a1,a2 = map(int,input().split())
b1,b2 = map(int,input().split())
c1 = b1-a1
c2 = b2-a2

s = t1*c1
t = s + t2*c2
# print(c1,c2,s,t)
ans = -1
if s * t > 0:
    ans = 0
elif t == 0:
    ans=-10
else:
    if s > t:
        tt = abs(t)
        ans = -((-s / tt)//1)*2 - 1
        if s / tt - s//tt < 10**-25:
            ans += 1
    else:
        ss = abs(s)
        ans = -((-ss / t)//1)*2 - 1
        if ss / t -ss//t < 10**-25:
            ans += 1
if ans == -10:
    print("infinity")
else:
    print(int(ans))
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
A = list(map(int,input().split()))

S = [A[0] % k]
for i in range(1, n):
    S.append((A[i]+S[-1]) % k)

# print(S)

D = {}
S = [0] + S
ans = 0
for i in range(len(S)):
    key = (S[i] - i) % k

    
    if i >= k:
        j = i-k
        key1 = (S[j] - j) % k
        D[key1] -= 1
        try:
            ans += D[key1]
            # print(i, j, D[key1])
        except:
            ans += 0

    try:
        D[key] += 1
    except:
        D[key] = 1

for j in range(len(S)-k, len(S)):
    key1 = (S[j] - j) % k
    D[key1] -= 1
    try:
        ans += D[key1]
        # print(i, j, D[key1])
    except:
        ans += 0
# print(D)
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
A = list(map(int,input().split()))

S = [A[0] % k]
for i in range(1, n):
    S.append((A[i]+S[-1]) % k)

# print(S)

D = {}
S = [0] + S
ans = 0
for i in range(len(S)):
    key = (S[i] - i) % k

    if i >= k:
        j = i-k
        key1 = (S[j] - j) % k
        D[key1] -= 1
        try:
            ans += D[key1]
            # print(i, j, D[key1])
        except:
            ans += 0

    try:
        D[key] += 1
    except:
        D[key] = 1

for j in range(max(0, len(S)-k), len(S)):
    key1 = (S[j] - j) % k
    D[key1] -= 1
    try:
        ans += D[key1]
        # print(i, j, D[key1])
    except:
        ans += 0
# print(D)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
S = [0] * n

for i in range(m):
    for j in range(2):
        C[i][j] -= 1

for i in range(m):
    S[C[i][0]] += 1
    S[C[i][1]] -= 1

for i in range(1, n):
    S[i] += S[i-1]

for i in range(n-1):
    if S[i] > 0:
        C.append([i+1, i, 0])

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]].append([C[i][1], C[i][2]])
    if C[i][2] > 0:
        M[C[i][1]].append([C[i][0], C[i][2]])

import heapq

D = [float("inf")] * n
P = [-1] * n
D[0] = 0
V = [0] * n
Q = []
for v in range(n):
    heapq.heappush(Q, [D[v], v])

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    le -= 1
    u = q[1]
    du = q[0]
    V[u] = 1
    for i in range(len(M[u])):
        v = M[u][i][0]
        luv = M[u][i][1]
        if V[v] == 0:
            alt = du + luv
            if D[v] > alt:
                D[v] = alt
                P[v] = u
                heapq.heappush(Q, [alt, v])
                le += 1

ans = D[-1]
if ans == float("inf"):
    ans = -1
print(ans)


Fixed submission:
import sys
input = sys.stdin.readline
n, m = map(int,input().split())
C = [list(map(int,input().split())) for i in range(m)]
S = [0] * n

for i in range(m):
    for j in range(2):
        C[i][j] -= 1

for i in range(m):
    S[C[i][0]] += 1
    S[C[i][1]] -= 1

for i in range(1, n):
    S[i] += S[i-1]

for i in range(n-1):
    if S[i] > 0:
        C.append([i+1, i, 0])

M = [[] for i in range(n)]
for i in range(len(C)):
    M[C[i][0]].append([C[i][1], C[i][2]])
    if C[i][2] > 0:
        M[C[i][1]].append([C[i][0], C[i][2]])

import heapq

D = [float("inf")] * n
P = [-1] * n
D[0] = 0
V = [0] * n
Q = []
for v in range(n):
    heapq.heappush(Q, [D[v], v])

le = len(Q)
while le > 0:
    q = heapq.heappop(Q)
    u = q[1]
    du = q[0]
    if V[u] == 0:
        V[u] = 1
        le -= 1
        for i in range(len(M[u])):
            v = M[u][i][0]
            luv = M[u][i][1]
            if V[v] == 0:
                alt = du + luv
                if D[v] > alt:
                    D[v] = alt
                    P[v] = u
                    heapq.heappush(Q, [alt, v])

ans = D[-1]
if ans == float("inf"):
    ans = -1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
L = list(map(int,input().split()))
L.sort(reverse=True)

# print(L)
ans = 0
for i in range(n):
    # print(i)
    a = L[i]
    ci = 0
    for j in range(i+1,n-1):
        b = L[j]
        ci = n-1
        # print("ci",ci)
        while ci > j and b+L[ci] <= a:
            ci -= 1
        ans += ci-j
print(ans)



Fixed submission:
n = int(input())
L = list(map(int,input().split()))
L.sort(reverse=True)

# print(L)
ans = 0
for i in range(n):
    # print(i)
    a = L[i]
    ci = n-1
    for j in range(i+1,n-1):
        b = L[j]
        ci = max(ci,j)
        # print("ci",ci)
        while ci > j and b+L[ci] <= a:
            ci -= 1
        ans += ci-j
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
a, b = map(int,input().split())

while a!=0 and b!=0:
    a,b = max(a,b),min(a,b)
    a %= b

ans = 1
for i in range(2, b+1):
    t = 0
    while b % i == 0:
        b //= i
        # print(b)
        t = 1
        if b==1:
            break
    ans += t
    if b==1:
        break
    
print(ans)

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

while a!=0 and b!=0:
    a,b = max(a,b),min(a,b)
    a %= b

# print(b)

bb = b

ans = 1
i = 2
end = int((b+1)**0.5)+2
while i < end:
    t = 0
    while b % i == 0:
        b //= i
        # print(b)
        t = 1
        end = int((b+1)**0.5)+2
        if b==1:
            break
    ans += t
    if b==1:
        break
    i += 1

if b != 1 and bb != 1:
    ans += 1
    
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from scipy.sparse.csgraph import dijkstra

n, m = map(int,input().split())
A = []
C = []
for i in range(m):
    ab = list(map(int,input().split()))
    A.append(ab)
    cc = list(map(int,input().split()))
    C.append(cc)

M = [[float("inf")] * 2**n for i in range(2**n)]

for i in range(2**n):
    M[i][i] = 0

for i in range(m):
    t = 0
    for j in C[i]:
        t += 2**(j-1)
    for j in range(2**n):
        for k in range(2**n):
            if (t-(k-j)) ^ (k-j) == t:
                # print(t,j)
                M[j][k] = min(M[j][k], A[i][0])
# print(M)

d = dijkstra(M, indices = 0)

ans = d[-1]
if ans == float("inf"):
    ans = -1
print(int(ans))


Fixed submission:
n, m = map(int,input().split())
A = []
C = []
for i in range(m):
    ab = list(map(int,input().split()))
    A.append(ab)
    cc = list(map(int,input().split()))
    C.append(cc)
T = []
for i in range(m):
    t = 0
    for j in C[i]:
        t += 2**(j-1)
    T.append(t)


n2 = 2**n

DP = [[float("inf") for i in range(n2)] for j in range(m+1)]
for i in range(m+1):
    DP[i][0] = 0

for i in range(1,m+1):
    t = T[i-1]
    for j in range(n2):
        # print(i,j,t)
        # print(DP[i][j|t], DP[i-1][j|t], DP[i-1][j] + A[i-1][0])
        DP[i][j|t] = min(DP[i][j|t], DP[i-1][j|t], DP[i-1][j] + A[i-1][0])
        DP[i][j] = min(DP[i][j], DP[i-1][j])
        # print(DP[i][j|t])

ans = DP[-1][-1]
if ans == float("inf"):
    ans = -1
print(int(ans))

Buggy python submission (verdict: Runtime Error):
from scipy.sparse.csgraph import dijkstra

n, m = map(int,input().split())
A = []
C = []
for i in range(m):
    ab = list(map(int,input().split()))
    A.append(ab)
    cc = list(map(int,input().split()))
    C.append(cc)

M = [[float("inf")] * 2**n for i in range(2**n)]

for i in range(2**n):
    M[i][i] = 0

for i in range(m):
    t = 0
    for j in C[i]:
        t += 2**(j-1)
    for j in range(2**n):
        for k in range(2**n):
            if (t-(k-j)) ^ (k-j) == t:
                # print(t,j)
                M[j][k] = min(M[j][k], A[i][0])
# print(M)

d = dijkstra(M, indices = 0)

ans = d[-1]
if ans == float("inf"):
    ans = -1
print(int(ans))


Fixed submission:
n, m = map(int,input().split())
A = []
C = []
for i in range(m):
    ab = list(map(int,input().split()))
    A.append(ab)
    cc = list(map(int,input().split()))
    C.append(cc)
T = []
for i in range(m):
    t = 0
    for j in C[i]:
        t += 2**(j-1)
    T.append(t)


n2 = 2**n

DP = [[float("inf") for i in range(n2)] for j in range(m+1)]
for i in range(m+1):
    DP[i][0] = 0

for i in range(1,m+1):
    t = T[i-1]
    for j in range(n2):
        # print(i,j,t)
        # print(DP[i][j|t], DP[i-1][j|t], DP[i-1][j] + A[i-1][0])
        DP[i][j|t] = min(DP[i][j|t], DP[i-1][j|t], DP[i-1][j] + A[i-1][0])
        DP[i][j] = min(DP[i][j], DP[i-1][j])
        # print(DP[i][j|t])

ans = DP[-1][-1]
if ans == float("inf"):
    ans = -1
print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):

n = int(input())

ans = 0
for i in range(n):
    ans += i
print(ans)

Fixed submission:

n = int(input())

print(n*(n-1)//2)
Buggy python submission (verdict: Runtime Error):
import math

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

X2 = []
for i in range(n):
    if X[i] != [0, 0]:
        X2.append(X[i][:])

X = X2[:]

n = len(X)

for i in range(n):
    X[i].append(math.atan2(X[i][1], X[i][0]))

X.sort(key=lambda x:x[2])

X += X[:]
#print(X)
ans = 0

X_sum = [[X[0][0], X[0][1]]]
for i in range(1, 2*n):
    #print(i)
    X_sum.append([X_sum[i-1][0] + X[i][0], X_sum[i-1][1] + X[i][1]])

#print(len(X_sum))

for st in range(0, n):
    for en in range(st+1, st+n+1):
        dis = [0, 0]
        for i in range(st, en):
            #print(i)
            dis[0] = X_sum[en][0] - X_sum[st][0]
            dis[1] = X_sum[en][1] - X_sum[st][1]
        #print(st,en,(dis[0]**2 + dis[1]**2)**0.5)
        ans = max(ans, (dis[0]**2 + dis[1]**2))


print(ans ** 0.5)

Fixed submission:
import math

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

X2 = []
for i in range(n):
    if X[i] != [0, 0]:
        X2.append(X[i][:])

X = X2[:]

n = len(X)

if n == 0:
    print(0)
else:

    for i in range(n):
        X[i].append(math.atan2(X[i][1], X[i][0]))

    X.sort(key=lambda x:x[2])

    X += X[:]
    #print(X)
    ans = 0

    X_sum = [[X[0][0], X[0][1]]]
    for i in range(1, 2*n):
        #print(i)
        X_sum.append([X_sum[i-1][0] + X[i][0], X_sum[i-1][1] + X[i][1]])

    #print(len(X_sum))

    for st in range(0, n):
        for en in range(st+1, st+n+1):
            dis = [0, 0]
            for i in range(st, en):
                #print(i)
                dis[0] = X_sum[en][0] - X_sum[st][0]
                dis[1] = X_sum[en][1] - X_sum[st][1]
            #print(st,en,(dis[0]**2 + dis[1]**2)**0.5)
            ans = max(ans, (dis[0]**2 + dis[1]**2))


    print(ans ** 0.5)
Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n-1)]
P = [list(map(int,input().split())) for i in range(q)]

ANS = [0] * (n+1)

C_plus = [0] * (n+1)
for i in range(q):
    C_plus[P[i][0]] += P[i][1]

E = [[] for i in range(n+1)]
V = [0] * (n+1)
Q = [1]
t = 0

V[1] = 1
ANS[1] = C_plus[1]

for i in range(n-1):
    E[A[i][0]].append(A[i][1])
    E[A[i][1]].append(A[i][0])

def tansaku(x):
    for i in E[x]:
        if V[i] == 0:
            ANS[i] = C_plus[i] + ANS[x]
            V[i] = 1
            Q.append(i)
            #print(Q)

while t < len(Q):
    tansaku(Q[t])
    t += 1

#print(ANS)

for i in range(n+1):
    ANS[i] = str(ANS[i])
print(" ".join(ANS[1:]))

Fixed submission:
n, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n-1)]
P = [list(map(int,input().split())) for i in range(q)]

ANS = [0] * (n+1)

C_plus = [0] * (n+1)
for i in range(q):
    C_plus[P[i][0]] += P[i][1]

E = [[] for i in range(n+1)]
V = [0] * (n+1)
Q = [0] * (n+2)
Q[0] = 1
t = 0
r = 1

V[1] = 1
ANS[1] = C_plus[1]

for i in range(n-1):
    E[A[i][0]].append(A[i][1])
    E[A[i][1]].append(A[i][0])

def tansaku(x):
    global r
    for i in E[x]:
        if V[i] == 0:
            ANS[i] = C_plus[i] + ANS[x]
            V[i] = 1
            Q[r] = i
            r += 1
            #print(Q)

while t != r:
    tansaku(Q[t])
    t += 1

#print(ANS)

for i in range(n+1):
    ANS[i] = str(ANS[i])
print(" ".join(ANS[1:]))

Buggy python submission (verdict: Time Limit Exceeded):
n, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n-1)]
P = [list(map(int,input().split())) for i in range(q)]

ANS = [0] * (n+1)

C_plus = [0] * (n+1)
for i in range(q):
    C_plus[P[i][0]] += P[i][1]

oya = [0] * (n+1)
E = [[] for i in range(n+1)]
V = [0] * (n+1)
Q = [1]
t = 0

V[1] = 1
ANS[1] = C_plus[1]

for i in range(n-1):
    E[A[i][0]].append(A[i][1])
    E[A[i][1]].append(A[i][0])

def tansaku(x):
    for i in E[x]:
        if V[i] == 0:
            oya[i] = x
            ANS[i] = C_plus[i] + ANS[x]
            V[i] = 1
            Q.append(i)
            #print(Q)

while t < len(Q):
    tansaku(Q[t])
    t += 1

#print(ANS)

for i in range(n+1):
    ANS[i] = str(ANS[i])
print(" ".join(ANS[1:]))

Fixed submission:
n, q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(n-1)]
P = [list(map(int,input().split())) for i in range(q)]

ANS = [0] * (n+1)

C_plus = [0] * (n+1)
for i in range(q):
    C_plus[P[i][0]] += P[i][1]

E = [[] for i in range(n+1)]
V = [0] * (n+1)
Q = [0] * (n+2)
Q[0] = 1
t = 0
r = 1

V[1] = 1
ANS[1] = C_plus[1]

for i in range(n-1):
    E[A[i][0]].append(A[i][1])
    E[A[i][1]].append(A[i][0])

def tansaku(x):
    global r
    for i in E[x]:
        if V[i] == 0:
            ANS[i] = C_plus[i] + ANS[x]
            V[i] = 1
            Q[r] = i
            r += 1
            #print(Q)

while t != r:
    tansaku(Q[t])
    t += 1

#print(ANS)

for i in range(n+1):
    ANS[i] = str(ANS[i])
print(" ".join(ANS[1:]))
Buggy python submission (verdict: Runtime Error):
n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]

C = [[] for i in range(10**4+10)]

for i in range(n):
    C[B[i][0]].append(B[i][1])
for i in range(len(C)):
    C[i].sort(reverse=1)

#print(C[:10])
notst=1
st=0
ans = 0

Bl = [0 for i in range(10**4+2)]
for i in range(1, m+1):
    for j in range(len(C[i])):
        Bl[C[i][j]] += 1
    if notst == 1 and len(C[i]) > 0:
        notst = 0
        st = C[i][0]
    if notst == 0 and len(C[i]) > 0:
        if st < C[i][0]:
            st = C[i][0]
    while st > 0 and Bl[st] == 0:
        st -= 1
    ans += st
    # print(ans)
    # print(Bl[:10])
    Bl[st] -= 1

print(ans)

    
    

Fixed submission:
n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]

C = [[] for i in range(10**5+10)]

for i in range(n):
    C[B[i][0]].append(B[i][1])
for i in range(len(C)):
    C[i].sort(reverse=1)

#print(C[:10])
notst=1
st=0
ans = 0

Bl = [0 for i in range(10**4+2)]
for i in range(1, m+1):
    for j in range(len(C[i])):
        Bl[C[i][j]] += 1
    if notst == 1 and len(C[i]) > 0:
        notst = 0
        st = C[i][0]
    if notst == 0 and len(C[i]) > 0:
        if st < C[i][0]:
            st = C[i][0]
    while st > 0 and Bl[st] == 0:
        st -= 1
    ans += st
    # print(ans)
    # print(Bl[:10])
    Bl[st] -= 1

print(ans)

Buggy python submission (verdict: Runtime Error):
n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]

C = [[] for i in range(10*5+2)]

for i in range(n):
    C[B[i][0]].append(B[i][1])
for i in range(len(C)):
    C[i].sort(reverse=1)

#print(C[:10])
notst=1
st=0
ans = 0

Bl = [0 for i in range(10**4+2)]
for i in range(1, m+1):
    for j in range(len(C[i])):
        Bl[C[i][j]] += 1
    if notst == 1 and len(C[i]) > 0:
        notst = 0
        st = C[i][0]
    if notst == 0 and len(C[i]) > 0:
        if st < C[i][0]:
            st = C[i][0]
    while st > 0 and Bl[st] == 0:
        st -= 1
    ans += st
    # print(ans)
    # print(Bl[:10])
    Bl[st] -= 1

print(ans)

    
    

Fixed submission:
n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]

C = [[] for i in range(10**5+10)]

for i in range(n):
    C[B[i][0]].append(B[i][1])
for i in range(len(C)):
    C[i].sort(reverse=1)

#print(C[:10])
notst=1
st=0
ans = 0

Bl = [0 for i in range(10**4+2)]
for i in range(1, m+1):
    for j in range(len(C[i])):
        Bl[C[i][j]] += 1
    if notst == 1 and len(C[i]) > 0:
        notst = 0
        st = C[i][0]
    if notst == 0 and len(C[i]) > 0:
        if st < C[i][0]:
            st = C[i][0]
    while st > 0 and Bl[st] == 0:
        st -= 1
    ans += st
    # print(ans)
    # print(Bl[:10])
    Bl[st] -= 1

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

n = int(input())
A = [int(input()) for i in range(n)]

Q = [A[0]] + [float("inf")] * (n+1)
le = 1
for i in range(1, n):
    if Q[le-1] >= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        ind = bisect.bisect_left(Q[:le][::-1], A[i])
        Q[le-ind] = A[i]
    # print(Q[:10])

print(le)

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

Q = [-float("inf"), A[0]] + [float("inf")] * (n+1)
le = 2
for i in range(1, n):
    if Q[le-1] >= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        l = 0
        r = le
        m = (l+r)//2
        while r-l > 1:
            if Q[m] >= A[i]:
                l = m
            else:
                r = m
            m = (l+r)//2
        Q[l+1] = A[i]
    # print(Q[:10])

print(le-1)

Buggy python submission (verdict: Runtime Error):
n = int(input())
A = [int(input()) for i in range(n)]

AA=[]
for i in range(n):
    AA.append([A[i],i])

A = AA[:]
A.sort(key=lambda x:x[0])

mm = 10**5+10
B=[0 for i in range(mm)]
for i in range(n):
    if A[i]<=mm:
        B[A[i]]+=1
        mm=A[i]
    else:
        t=A[i]
        while B[t]==0:
            t-=1
        B[t]-=1
        B[A[i]]+=1
        #print(B)
        if mm==t and B[t]==0:
            while B[mm]==0:
                mm+=1
print(sum(B))

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

Q = [-float("inf"), A[0]] + [float("inf")] * (n+1)
le = 2
for i in range(1, n):
    if Q[le-1] >= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        l = 0
        r = le
        m = (l+r)//2
        while r-l > 1:
            if Q[m] >= A[i]:
                l = m
            else:
                r = m
            m = (l+r)//2
        Q[l+1] = A[i]
    # print(Q[:10])

print(le-1)

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


mm = max(A)+2
B=[0 for i in range(mm)]
for i in range(n):
    if A[i]<=mm:
        B[A[i]]+=1
        mm=A[i]
    else:
        t=A[i]
        while B[t]==0:
            t-=1
        B[t]-=1
        B[A[i]]+=1
        #print(B)
        if mm==t and B[t]==0:
            while B[mm]==0:
                mm+=1
print(sum(B))

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

Q = [-float("inf"), A[0]] + [float("inf")] * (n+1)
le = 2
for i in range(1, n):
    if Q[le-1] >= A[i]:
        Q[le] = A[i]
        le += 1
    else:
        l = 0
        r = le
        m = (l+r)//2
        while r-l > 1:
            if Q[m] >= A[i]:
                l = m
            else:
                r = m
            m = (l+r)//2
        Q[l+1] = A[i]
    # print(Q[:10])

print(le-1)