Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10000)
n = int(input())
*A, = map(int, input().split())
DP = [[None for j in range(n+1)] for i in range(n)]
def dp(i, j):
    if i == j:
        return 0
    if DP[i][j] != None:
        return DP[i][j]
    DP[i][j] = max(A[i]-dp(i+1, j), A[j-1]-dp(i, j-1))
    return DP[i][j]
print(dp(0, n))


Fixed submission:
n = int(input())
*A, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        DP[i][i+l] = max(A[i]-DP[i+1][i+l], A[i+l-1]-DP[i][i+l-1])
print(DP[0][n])

Buggy python submission (verdict: Runtime Error):
n = int(input())
*A, = map(int, input().split())
DP = [[None for j in range(n+1)] for i in range(n)]
def dp(i, j):
    if i == j:
        return 0
    if DP[i][j] != None:
        return DP[i][j]
    DP[i][j] = max(A[i]-dp(i+1, j), A[j-1]-dp(i, j-1))
    return DP[i][j]
print(dp(0, n))


Fixed submission:
n = int(input())
*A, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        DP[i][i+l] = max(A[i]-DP[i+1][i+l], A[i+l-1]-DP[i][i+l-1])
print(DP[0][n])

Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(10**5)
n = int(input())
*A, = map(int, input().split())
DP = [[None for j in range(n+1)] for i in range(n+1)]


def dp(i, j):
    if j <= i:
        DP[i][j] = 0
    if DP[i][j] != None:
        return DP[i][j]
    DP[i][j] = max(A[i]-dp(i+1, j), A[j-1]-dp(i, j-1))
    return DP[i][j]


print(dp(0, n))


Fixed submission:
n = int(input())
*A, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        DP[i][i+l] = max(A[i]-DP[i+1][i+l], A[i+l-1]-DP[i][i+l-1])
print(DP[0][n])

Buggy python submission (verdict: Runtime Error):
def dp(i, j):
    if i == j:
        return A[i]
    return max(A[i]-dp(i+1, j), A[j]-dp(i, j-1))


n = int(input())
*A, = map(int, input().split())
print(dp(0, n-1))


Fixed submission:
n = int(input())
*A, = map(int, input().split())
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for l in range(1, n+1):
    for i in range(n-l+1):
        DP[i][i+l] = max(A[i]-DP[i+1][i+l], A[i+l-1]-DP[i][i+l-1])
print(DP[0][n])
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9+7
DP = [[None for j in range(k+1)] for i in range(n+1)]
for i in range(n+1):
    DP[i][0] = 1
for j in range(1, k+1):
    DP[0][j] = 0
for i in range(1, n+1):
    for j in range(1, k+1):
        DP[i][j] = (DP[i][j-1]+DP[i-1][j]) % p
        if j > A[i-1]:
            DP[i][j] = (DP[i][j]-DP[i-1][j-1-A[i-1]]) % p
print(DP[n][k])


Fixed submission:
n, k = map(int, input().split())
*A, = map(int, input().split())
p = 10**9+7
DP = [[None for j in range(k+1)] for i in range(n+1)]
for i in range(n+1):
    DP[i][0] = 1
for j in range(1, k+1):
    DP[0][j] = 0
for i in range(1, n+1):
    for j in range(1, k+1):
        DP[i][j] = (DP[i][j-1]+DP[i-1][j]) % p
        if j > A[i-1]:
            DP[i][j] = (DP[i][j]-DP[i-1][j-1-A[i-1]]) % p
print(DP[n][k])
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
*A, = map(int, input().split())
# n = 4
# A = [10, 20, 30, 40]
inf = 10**20
DP = [[None for r in range(n+1)] for l in range(n)]
S = [0]
for i in range(n):
    S.append(S[-1]+A[i])


def f(l, r):
    if r <= l+1:
        DP[l][r] = 0
    if DP[l][r] != None:
        return DP[l][r]
    DP[l][r] = S[r]-S[l]+min([f(l, i)+f(i, r) for i in range(l+1, r)])
    return DP[l][r]


print(f(0, n))


Fixed submission:
n = int(input())
*A, = map(int, input().split())
# n = 4
# A = [10, 20, 30, 40]
inf = 10**20
DP = [[None for r in range(n+1)] for l in range(n)]
S = [0]
for i in range(n):
    S.append(S[-1]+A[i])


def f(l, r):
    if r <= l+1:
        DP[l][r] = 0
    if DP[l][r] != None:
        return DP[l][r]
    DP[l][r] = S[r]-S[l]+min([f(l, i)+f(i, r) for i in range(l+1, r)])
    return DP[l][r]


print(f(0, n))
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10000)
n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
p = 10**9+7
Q = [0]
V = [False for i in range(n)]
C = [[] for i in range(n)]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            C[x].append(y)
            Q.append(y)
DP = [[None, None] for i in range(n)]
def dp(i, c):
    if DP[i][c] != None:
        return DP[i][c]
    tmp = 1
    for j in C[i]:
        if c == 0:
            tmp = (tmp*(dp(j, 0)+dp(j, 1))) % p
        else:
            tmp = (tmp*dp(j, 0)) % p
    DP[i][c] = tmp
    return DP[i][c]
print(dp(0, 0)+dp(0, 1))


Fixed submission:
import sys
sys.setrecursionlimit(100000)
n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
p = 10**9+7
Q = [0]
V = [False for i in range(n)]
C = [[] for i in range(n)]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            C[x].append(y)
            Q.append(y)
DP = [[None, None] for i in range(n)]
def dp(i, c):
    if DP[i][c] != None:
        return DP[i][c]
    tmp = 1
    for j in C[i]:
        if c == 0:
            tmp = (tmp*(dp(j, 0)+dp(j, 1))) % p
        else:
            tmp = (tmp*dp(j, 0)) % p
    DP[i][c] = tmp
    return DP[i][c]
print((dp(0, 0)+dp(0, 1))%p)

Buggy python submission (verdict: Runtime Error):
n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
p = 10**9+7
Q = [0]
V = [False for i in range(n)]
C = [[] for i in range(n)]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            C[x].append(y)
            Q.append(y)
DP = [[None, None] for i in range(n)]
def dp(i, c):
    if DP[i][c] != None:
        return DP[i][c]
    tmp = 1
    for j in C[i]:
        if c == 0:
            tmp = (tmp*(dp(j, 0)+dp(j, 1))) % p
        else:
            tmp = (tmp*dp(j, 0)) % p
    DP[i][c] = tmp
    return DP[i][c]
print(dp(0, 0)+dp(0, 1))


Fixed submission:
import sys
sys.setrecursionlimit(100000)
n = int(input())
G = [[] for i in range(n)]
for i in range(n-1):
    x, y = map(int, input().split())
    G[x-1].append(y-1)
    G[y-1].append(x-1)
p = 10**9+7
Q = [0]
V = [False for i in range(n)]
C = [[] for i in range(n)]
while Q:
    x = Q.pop()
    V[x] = True
    for y in G[x]:
        if not V[y]:
            C[x].append(y)
            Q.append(y)
DP = [[None, None] for i in range(n)]
def dp(i, c):
    if DP[i][c] != None:
        return DP[i][c]
    tmp = 1
    for j in C[i]:
        if c == 0:
            tmp = (tmp*(dp(j, 0)+dp(j, 1))) % p
        else:
            tmp = (tmp*dp(j, 0)) % p
    DP[i][c] = tmp
    return DP[i][c]
print((dp(0, 0)+dp(0, 1))%p)
Buggy python submission (verdict: Time Limit Exceeded):
class SegmentTree:
    def __init__(self, A, n=18, inf=10**20):
        l = len(A)
        self.size = n
        self.array = [inf]*(2**(n+1)-1)
        for i in range(l):
            self.array[i+2**n-1] = A[i]
        for i in range(2**n-2, -1, -1):
            self.array[i] = max(self.array[2*i+1], self.array[2*i+2])

    def _subquery(self, l, r, k, i, j):
        if j <= l or r <= i:
            return 0
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_max = self._subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_max = self._subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return max(l_max, r_max)

    def max(self, l, r):
        return self._subquery(l, r, 0, 0, 2**self.size)

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = c
        while tmp > 0:
            tmp = (tmp - 1) // 2
            l = self.array[2 * tmp + 1]
            r = self.array[2 * tmp + 2]
            self.array[tmp] = max(l, r)

n = int(input())
*H, = map(lambda x: int(x)-1, input().split())
*A, = map(int, input().split())
DP = SegmentTree([0]*n)
for i in range(n):
    tmp = DP.max(0, H[i])
    DP.update(H[i], tmp+A[i])
print(DP.max(0, n))


Fixed submission:
class SegmentTree:
    def __init__(self, A, n=18, inf=10**20):
        l = len(A)
        self.size = n
        self.array = [inf]*(2**(n+1)-1)
        for i in range(l):
            self.array[i+2**n-1] = A[i]
        for i in range(2**n-2, -1, -1):
            self.array[i] = max(self.array[2*i+1], self.array[2*i+2])

    def _subquery(self, l, r, k, i, j):
        if j <= l or r <= i:
            return 0
        elif l <= i and j <= r:
            return self.array[k]
        else:
            l_max = self._subquery(l, r, 2 * k + 1, i, (i + j) // 2)
            r_max = self._subquery(l, r, 2 * k + 2, (i + j) // 2, j)
            return max(l_max, r_max)

    def max(self, l, r):
        return self._subquery(l, r, 0, 0, 2**self.size)

    def update(self, i, c):
        tmp = i + 2**self.size - 1
        self.array[tmp] = c
        while tmp > 0:
            tmp = (tmp - 1) // 2
            l = self.array[2 * tmp + 1]
            r = self.array[2 * tmp + 2]
            self.array[tmp] = max(l, r)

n = int(input())
*H, = map(lambda x: int(x)-1, input().split())
*A, = map(int, input().split())
DP = SegmentTree([0]*n)
for i in range(n):
    tmp = DP.max(0, H[i])
    DP.update(H[i], tmp+A[i])
print(DP.max(0, n))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
S = input()
p = 10**9+7
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for j in range(n):
    DP[1][j] = 1
for i in range(2, n+1):
    A = [0]
    for j in range(n):
        A.append(A[-1]+DP[i-1][j])
    for j in range(n-i+1):
        if S[i-2] == '<':
            DP[i][j] = (A[n-(i-1)+1]-A[j+1]) % p
        else:
            DP[i][j] = A[j+1] % p
print(DP[n][0])


Fixed submission:
n = int(input())
S = input()
p = 10**9+7
DP = [[0 for j in range(n+1)] for i in range(n+1)]
for j in range(n):
    DP[1][j] = 1
for i in range(2, n+1):
    A = [0]
    for j in range(n):
        A.append(A[-1]+DP[i-1][j])
    for j in range(n-i+1):
        if S[i-2] == '<':
            DP[i][j] = (A[n-(i-1)+1]-A[j+1]) % p
        else:
            DP[i][j] = A[j+1] % p
print(DP[n][0])
Buggy python submission (verdict: Runtime Error):
N,M=map(int,input().split())
data=[]
for m in range(M):
    data.append(list(map(int,input().split())))
    data[m].append(m)
data.sort(key=lambda x:x[1])

pref=0
for m in range(M):
    count+=1
    if data[m][0]!=pref:
        count=1
    pref=data[m][0]
    ID=('000000'+str(data[m][0]))[-6:]+('000000'+str(count))[-6:]
    data[m].append(ID)

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

for m in range(M):
    print(data[m][3])

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

data.sort(key=lambda x:x[1])
data.sort(key=lambda x:x[0])

pref=0
count=0
for m in range(M):
    count+=1
    if data[m][0]!=pref:
        count=1
    pref=data[m][0]
    ID=('000000'+str(data[m][0]))[-6:]+('000000'+str(count))[-6:]
    data[m].append(ID)

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

for m in range(M):
    print(data[m][3])
Buggy python submission (verdict: Time Limit Exceeded):
import numpy
N=int(input())
A=list(map(int,input().split()))
B=[A[i]-i for i in range(N)]
print(sum([abs(b-int(numpy.median(B))) for b in B]))

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
B=sorted([A[i]-i for i in range(N)])
if N%2==0:
	C=int((B[int(N/2)]+B[int(N/2-1)])/2)
else:
	C=B[int((N-1)/2)]
print(sum([abs(b-C) for b in B]))

Buggy python submission (verdict: Runtime Error):
N=int(input())
A=list(map(int,input().split()))
B=[A[i]-i for i in range(N)]
C=median(B)
print(sum([b-C for b in B]))

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
B=sorted([A[i]-i for i in range(N)])
if N%2==0:
	C=int((B[int(N/2)]+B[int(N/2-1)])/2)
else:
	C=B[int((N-1)/2)]
print(sum([abs(b-C) for b in B]))
Buggy python submission (verdict: Runtime Error):
A,B=input().split()
print(max([A+B,A-B,A*B]))

Fixed submission:
A,B=map(int,input().split())
print(max([A+B,A-B,A*B]))
Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
S=[input() for i in range(H)]
ans="No"
for i in range(H):
    for j in range(W):
        if S[i][j]=='#':
            if i>0 and S[i-1][j]=='#':
                ans="Yes"
            if i<H-1 and S[i+1][j]=='#':
                ans="Yes"
            if j>0 and S[i][j-1]=='#':
                ans="Yes"
            if j<W-1 and S[i][j+1]='#':
                ans="Yes"
print(ans)

Fixed submission:
H,W=map(int,input().split())
S=[input() for i in range(H)]
ans="Yes"
for i in range(H):
    for j in range(W):
        Tonari=[]
        if i>0:
            Tonari.append(S[i-1][j])
        if i<H-1:
            Tonari.append(S[i+1][j])
        if j>0:
            Tonari.append(S[i][j-1])
        if j<W-1:
            Tonari.append(S[i][j+1])
        if S[i][j]=='#' and all([t=='.' for t in Tonari]):
            ans="No"
print(ans)

Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
S=[input() for i in range(H)]
ans="No"
for i in range(W):
    for j in range(H):
        if S[i][j]=='#':
            if i>0 and S[i-1][j]=='#':
                ans="Yes"
            if i<W-1 and S[i+1][j]=='#':
                ans="Yes"
            if j>0 and S[i][j-1]=='#':
                ans="Yes"
            if j<H-1 and S[i][j+1]=='#':
                ans="Yes"
print(ans)

Fixed submission:
H,W=map(int,input().split())
S=[input() for i in range(H)]
ans="Yes"
for i in range(H):
    for j in range(W):
        Tonari=[]
        if i>0:
            Tonari.append(S[i-1][j])
        if i<H-1:
            Tonari.append(S[i+1][j])
        if j>0:
            Tonari.append(S[i][j-1])
        if j<W-1:
            Tonari.append(S[i][j+1])
        if S[i][j]=='#' and all([t=='.' for t in Tonari]):
            ans="No"
print(ans)

Buggy python submission (verdict: Runtime Error):
H,W=map(int,input().split())
S=[input() for i in range(H)]
ans="Yes"
for i in range(W):
    for j in range(H):
        Tonari=[]
        if i>0:
            Tonari.append(S[i-1][j])
        if i<W-1:
            Tonari.append(S[i+1][j])
        if j>0:
            Tonari.append(S[i][j-1])
        if j<H-1:
            Tonari.append(S[i][j+1])
        if S[i][j]=='#' and all([t=='.' for t in Tonari]):
            ans="No"
print(ans)

Fixed submission:
H,W=map(int,input().split())
S=[input() for i in range(H)]
ans="Yes"
for i in range(H):
    for j in range(W):
        Tonari=[]
        if i>0:
            Tonari.append(S[i-1][j])
        if i<H-1:
            Tonari.append(S[i+1][j])
        if j>0:
            Tonari.append(S[i][j-1])
        if j<W-1:
            Tonari.append(S[i][j+1])
        if S[i][j]=='#' and all([t=='.' for t in Tonari]):
            ans="No"
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
count=0
for i in range(N):
    p=A[i]
    if p==0:
        count+=1
    for j in range(i+1,N):
        p+=A[j]
        if p==0:
            count+=1
print(count)

Fixed submission:
n = int(input())
*A, = map(int, input().split())
S = [0]
for i in range(n):
    S.append(S[-1] + A[i])
C = {}
for s in S:
    try:
        C[s] += 1
    except BaseException:
        C[s] = 1
print(sum([v * (v - 1) // 2 for v in C.values()]))
Buggy python submission (verdict: Time Limit Exceeded):
A,B,K=map(int,input().split())
i=A
while i<=B:
    if abs(i-A)<K or abs(i-B)<K:
        print(i)
    i+=1

Fixed submission:
A,B,K=map(int,input().split())
X=[i for i in range(A,min(B,A+K))]+[j for j in range(max(A,B-K+1),B+1)]
X=sorted(list(set(X)))
for x in X:print(x)
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
A=list(map(int,input().split()))
for i in range(N):
    B=[0]+A[0:i]+A[i+1:N]+[0]
    print(sum([abs(B[j]-B[j+1]) for j in range(N)]))

Fixed submission:
N=int(input())
A=list(map(int,input().split()))
A=[0]+A+[0]
cost=sum([abs(A[k]-A[k+1]) for k in range(N+1)])
for i in range(1,N+1):
    if A[i-1]<=A[i]<=A[i+1] or A[i-1]>=A[i]>=A[i+1]:
        print(cost)
    else:
        print(cost-abs(A[i-1]-A[i])-abs(A[i]-A[i+1])+abs(A[i-1]-A[i+1]))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
S={input() for i in range(N)}
count=0
for x in S:
    for y in S-{x}:
        for z in S-{x,y}:
            A={x[0],y[0],z[0]}
            if len(A)==3 and A<={'M','A','R','C','H'}:
                count+=1
print(int(count/6))

Fixed submission:
N=int(input())
S=[input() for i in range(N)]
m=len([s for s in S if s[0]=='M'])
a=len([s for s in S if s[0]=='A'])
r=len([s for s in S if s[0]=='R'])
c=len([s for s in S if s[0]=='C'])
h=len([s for s in S if s[0]=='H'])
count=0
march=[m,a,r,c,h]
for x in range(0,3):
    for y in range(x+1,4):
          for z in range(y+1,5):
                count+=march[x]*march[y]*march[z]
print(count)
Buggy python submission (verdict: Runtime Error):
S=input()
S[3]=8
print(S)

Fixed submission:
S=list(input())
S[3]='8'
print("".join(S))
Buggy python submission (verdict: Time Limit Exceeded):
N=int(input())
D=[int(i) for i in input().split()]
M=int(input())
T=[int(i) for i in input().split()]
x=0
for i in range(M):
    if T[i] in D:
        D.remove(T[i])
    else:
        x+=1
if x==0:
    print("YES")
else:
    print("NO")

Fixed submission:
n = int(input())
*D, = map(int, input().split())
m = int(input())
*T, = map(int, input().split())
D.sort()
T.sort()
j = 0
for i in range(n):
    if j == m:
        break
    if D[i] == T[j]:
        j += 1
if j == m:
    print('YES')
else:
    print('NO')
Buggy python submission (verdict: Runtime Error):
n = int(input())
# n = 100
m = 0
for i in range(1, n+1):
    a = i
    c = 0
    while a % 2 == 0:
        a = a//2
        c += 1
    if c > m:
        x = i
    m = max(m, c)
print(x)


Fixed submission:
n = int(input())
# n = 100
m = 0
x = 1
for i in range(1, n+1):
    a = i
    c = 0
    while a % 2 == 0:
        a = a//2
        c += 1
    if c > m:
        x = i
    m = max(m, c)
print(x)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = list(map(int, input().split()))

ans = 0
for i in range(n//2+1):
    if a[2*i] % 2 == 1:
        ans += 1
print(ans)


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

ans = 0
for i in range(n):
    if (i + 1)%2 == 1 and a[i] % 2 == 1:
        ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

s_a = [0]
s_b = [0]
for i in range(n):
    s_a.append(s_a[i] + a[i])
for i in range(m):
    s_b.append(s_b[i] + b[i])
    
ans = 0
ok = m
for i in range(n+1):
    for j in range(ok+1):
        if s_a[i] + s_b[j] <= k:
            ans = max(ans, i+j)
            tmp = j
    ok = tmp

print(ans)

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

s_a = [0]
s_b = [0]
for i in range(n):
    s_a.append(s_a[i] + a[i])
for i in range(m):
    s_b.append(s_b[i] + b[i])

ans = 0
tmp = m
for i in range(n+1):
    for j in range(tmp+1)[::-1]:
        if s_a[i] + s_b[j] <= k:
            ans = max(ans, i+j)
            tmp = j
            break
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
a.sort()
ls = [1]*(10**6+1)
cnt = [0]*(10**6+1)
for i in range(n):
    cnt[a[i]] += 1
    if ls[a[i]] == 1:
        for j in range(a[i]*2, 10**6+1, a[i]):
            ls[j] = 0
ans = 0
for i in range(n):
    if ls[a[i]] == 1 and cnt[a[i]] == 1:
        ans += 1
print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ls = [1] * (10 ** 6 + 1)
cnt = [0] * (10 ** 6 + 1)
for i in range(n):
    cnt[a[i]] += 1
    if cnt[a[i]] == 1:
        if ls[a[i]] == 1:
            for j in range(a[i] * 2, 10 ** 6 + 1, a[i]):
                ls[j] = 0
ans = 0
for i in range(n):
    if ls[a[i]] == 1 and cnt[a[i]] == 1:
        ans += 1
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
a.sort()
ls = [1]*(10**6+1)
for i in range(n):
    if ls[a[i]] == 1:
        for j in range(a[i]*2, 10**6+1, a[i]):
            ls[j] = 0
ans = 0
for i in range(n):
    if ls[a[i]] == 1 and a.count(a[i]) <= 1:
        ans += 1
print(ans)

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
a.sort()
ls = [1] * (10 ** 6 + 1)
cnt = [0] * (10 ** 6 + 1)
for i in range(n):
    cnt[a[i]] += 1
    if cnt[a[i]] == 1:
        if ls[a[i]] == 1:
            for j in range(a[i] * 2, 10 ** 6 + 1, a[i]):
                ls[j] = 0
ans = 0
for i in range(n):
    if ls[a[i]] == 1 and cnt[a[i]] == 1:
        ans += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))

ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        if j - i == a[i] + a[j]:
            ans += 1
print(ans)


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

ans = 0
dic1 = {}
dic2 = {}
for i in range(n):
    tmp1 = a[i] + (i + 1)
    tmp2 = -a[i] + (i + 1)
    if tmp1 in dic1:
        dic1[tmp1] += 1
    else:
        dic1[tmp1] = 1
    if tmp2 in dic2:
        dic2[tmp2] += 1
    else:
        dic2[tmp2] = 1
for key in dic1.keys():
    if key in dic2:
        ans += dic1[key] * dic2[key]
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
ans_list = []
for i in range(Q):
    l, r  = map(int, input().split())
    ans = 0
    for j in range(l-1, r-1):
        if S[j] == 'A':
            if S[j+1] == 'C':
                ans += 1
    print(ans)

Fixed submission:
N, Q = map(int, input().split())
S = input()
ls = [0]
for i in range(N-1):
    if S[i] == 'A' and S[i+1] == 'C':
        ls.append(ls[i] + 1)
    else:
        ls.append(ls[i])
for i in range(Q):
    l, r = map(int, input().split())
    print(ls[r-1] - ls[l-1])
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
h = list(int(input()) for i in range(N))

h.sort()
ans = float('inf')

for i in range(N - K + 1):
  temp = h[i + N - K] - h[i]
  if temp < ans:
    ans = temp

print(ans)


Fixed submission:
N, K = map(int, input().split())
h = list(int(input()) for i in range(N))

h.sort()
ans = float('inf')

for i in range(N - K + 1):
  temp = h[i + K - 1] - h[i]
  if temp < ans:
    ans = temp

print(ans)
Buggy python submission (verdict: Runtime Error):
D, N = map(int, input().split())

if N < 99:
  print(100**D*N)
elif N = 100:
  print(100**D*101)


Fixed submission:
D, N = map(int, input().split())

if N < 100:
  print(100**D*N)
elif N == 100:
  print(100**D*101)
Buggy python submission (verdict: Runtime Error):
n, a, b = map(int, input().split())

ans = 0
for i in range(1, n+1):
    sum = 0
    while i != 0:
        sun += i%10
        i = i//10
    if sum >= a and sum <= b:
        ans += i
print(ans)

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

ans = 0
for i in range(1, n+1):
    s = str(i)
    l = 0
    for j in range(len(s)):
        l += int(s[j])
    if l >= a and l <= b:
        ans += i
print(ans)

Buggy python submission (verdict: Runtime Error):
n, a, b = map(int, input().split())

ans = 0
for i in range(1, n+1):
    sum = 0
    while i != 0:
        sun += i%10]
        i = i//10
    if sum >= a and sum <= b:
        ans += i
print(ans)

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

ans = 0
for i in range(1, n+1):
    s = str(i)
    l = 0
    for j in range(len(s)):
        l += int(s[j])
    if l >= a and l <= b:
        ans += i
print(ans)