Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int ,input().split())
h = list(map(int, input().split()))

dp = [0] * n
dp[0] = 0
# 足場を一つづつ見ていく
for i in range(1, n):
#    for j in range(max(0,i-k),i):
#        # 今の足場へのコストと、他の足場から来た場合のコストを比較
#        dp[i] = min(dp[i], dp[j] + abs(h[i]-h[j]))
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i-k,0),i))
print(dp[-1])

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

dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i-k,0),i))
print(dp[-1])

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

dp = [float('inf')] * n
dp[0] = 0
# 足場を一つづつ見ていく
for i in range(1, n):
    for j in range(max(0,i-k),i):
        # 今の足場へのコストと、他の足場から来た場合のコストを比較
        dp[i] = min(dp[i], dp[j] + abs(h[i]-h[j]))
print(dp[-1])

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

dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i-k,0),i))
print(dp[-1])

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

dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i-k,0),i))
print(dp[-1])

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

dp = [0] * n
for i in range(1, n):
    dp[i] = min(dp[j] + abs(h[j] - h[i]) for j in range(max(i-k,0),i))
print(dp[-1])
Buggy python submission (verdict: Time Limit Exceeded):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j < wv[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wv[i][0]] + wv[i][1])
print(dp[N][W])

Fixed submission:
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j < wv[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wv[i][0]] + wv[i][1])
print(dp[N][W])
Buggy python submission (verdict: Time Limit Exceeded):
n,w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

sum_v = sum([wv[i][1] for i in range(n)])

# dp[i][j]: i番目の品物までで価値がj以上であるときの重さの最小値
dp = [[float('inf')]*(sum_v+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum_v+1):
        # 品物を選ぶ場合
        if (j - wv[i][1] >= 0):
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        # 品物を選ばない場合
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = 0
for i in range(sum_v+1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Fixed submission:
n,w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

sum_v = sum([wv[i][1] for i in range(n)])

# dp[i][j]: i番目の品物までで価値がj以上であるときの重さの最小値
dp = [[float('inf')]*(sum_v+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum_v+1):
        # 品物を選ぶ場合
        if (j - wv[i][1] >= 0):
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        # 品物を選ばない場合
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = 0
for i in range(sum_v+1):
    if dp[n][i] <= w:
        ans = i
print(ans)

Buggy python submission (verdict: Runtime Error):
N, W = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*(W+1) for _ in range(N+1)]

for i in range(N):
    for j in range(W+1):
        if j < wv[i][0]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wv[i][0]] + wv[i][1])
print(dp[N][W])

Fixed submission:
n,w = map(int, input().split())
wv = [list(map(int, input().split())) for _ in range(n)]

sum_v = sum([wv[i][1] for i in range(n)])

# dp[i][j]: i番目の品物までで価値がj以上であるときの重さの最小値
dp = [[float('inf')]*(sum_v+1) for _ in range(n+1)]
dp[0][0] = 0

for i in range(n):
    for j in range(sum_v+1):
        # 品物を選ぶ場合
        if (j - wv[i][1] >= 0):
            dp[i+1][j] = min(dp[i][j], dp[i][j-wv[i][1]] + wv[i][0])
        # 品物を選ばない場合
        dp[i+1][j] = min(dp[i+1][j], dp[i][j])
ans = 0
for i in range(sum_v+1):
    if dp[n][i] <= w:
        ans = i
print(ans)
Buggy python submission (verdict: Runtime Error):
d,g = map(int, input().split())

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

ans=float('inf')
for bit in range(2**d):
    b = 0
    score = 0
    num = 0
    # ボーナスを貰えるまで問題を解く場合を計算
    # bit探索し、ボーナスを貰うパターンを網羅する
    for i in range(d):
        if (bit >> i) & 1:
            # 問題を解いた点 + ボーナス
            score += pc[0][i] * (i+1) * 100 + pc[1][i]
            # 解いた問題数
            num += pc[0][i]
        else:
            # ボーナスを貰えるまで解かない問題の場合
            # この値には最終的にはボーナスを貰えるまでは解かない、最大点がもらえる問題の番号が入る
            b = i

    # ボーナスを貰えるまでは解かない問題による加点と回答の更新を行う
    for j in range(pc[b][0]):
        if score>=g and num<ans:
            ans=num
        score+=(b+1)*100
        num+=1

print(ans)

Fixed submission:
d,g = map(int, input().split())

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

ans=float('inf')
for bit in range(2**d):
    b = 0
    score = 0
    num = 0
    # ボーナスを貰えるまで問題を解く場合を計算
    # bit探索し、ボーナスを貰うパターンを網羅する
    for i in range(d):
        if (bit >> i) & 1:
            # 問題を解いた点 + ボーナス
            score += pc[i][0] * (i+1) * 100 + pc[i][1]
            # 解いた問題数
            num += pc[i][0]
        else:
            # ボーナスを貰えるまで解かない問題の場合
            # この値には最終的にはボーナスを貰えるまでは解かない、最大点がもらえる問題の番号が入る
            b = i

    # ボーナスを貰えるまでは解かない問題による加点と回答の更新を行う
    for j in range(pc[b][0]):
        if score>=g and num<ans:
            ans=num
        score+=(b+1)*100
        num+=1

print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
# M,A,R,C,H
num = [0] * 5
check_list = ['M','A','R','C','H']
for _ in range(n):
    s = input()
    for i, c in enumerate(check_list):
        if s[0] == c:
            num[i]+=1
            break
ans = 0
for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            ans += num[i]*num[j]*num[k]
print(ans)

Fixed submission:
n = int(input())
# M,A,R,C,H
num = [0] * 5
check_list = ['M','A','R','C','H']
for _ in range(n):
    s = input()
    for i, c in enumerate(check_list):
        if s[0] == c:
            num[i]+=1
            break
ans = 0
for i in range(5-2):
    for j in range(i+1, 5-1):
        for k in range(j+1, 5):
            ans += num[i]*num[j]*num[k]
print(ans)
Buggy python submission (verdict: Runtime Error):
n,s = map(int, input().split())

for x in range(n):
    for y in range(n):
        tmp = n-x-y
        tmp2 = s-x*10000-y*5000
        if tmp*1000 == tmp2 and tmp >= 0:
            print(f'{x} {y} {tmp}')
            exit(0)

print('-1 -1 -1')

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

for x in range(n+1):
    for y in range(n+1-x):
        tmp = n-x-y
        if (x*10000+y*5000+tmp*1000) == s:
            print('{} {} {}'.format(x,y,tmp))
            exit(0)

print('-1 -1 -1')

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

for x in range(n):
    for y in range(n):
        tmp = n-x-y
        tmp2 = s-x*10000-y*5000
        if tmp*1000 == tmp2:
            print(f'{x} {y} {tmp}')
            exit(0)

print('-1 -1 -1')

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

for x in range(n+1):
    for y in range(n+1-x):
        tmp = n-x-y
        if (x*10000+y*5000+tmp*1000) == s:
            print('{} {} {}'.format(x,y,tmp))
            exit(0)

print('-1 -1 -1')
Buggy python submission (verdict: Runtime Error):
n, c = map(int, input().split())
# input時に前処理として以下のことをしておく
#   * 開始時間を-1(-0.5の制約だが、-1しても変わらないので-1する)しておく

# テレビ局の番組をチャンネルごとに登録
r = [[0 for i in range(c)] for j in range(100)]
for _ in range(n):
    s,t,c = map(int, input().split())
    for j in range(s-1, t):
        r[j][c - 1] = 1
# print(*r,sep='\n')

ans = 0
for i in range(len(r)):
    ans = max(ans, sum(r[i]))
print(ans)


# 補足
# チャンネル数4の場合以下のような配列ができる
# 1行でとある時間のチャンネル状態(1: 録画する, 0: 録画しない)がつく
#[0, 0, 0, 0]
#[0, 0, 1, 0]
#[1, 1, 1, 0]  <- この時間で3チャンネル録画が必要
#[1, 1, 0, 0]  <- この時間で2チャンネル録画が必要
#[1, 1, 0, 0]
#[1, 0, 0, 0]

Fixed submission:
n, c = map(int, input().split())
# input時に前処理として以下のことをしておく
#   * 開始時間を-1(-0.5の制約だが、-1しても変わらないので-1する)しておく

# テレビ局の番組をチャンネルごとに登録
r = [[0 for i in range(c)] for j in range(100000)]
for _ in range(n):
    s,t,c = map(int, input().split())
    for j in range(s-1, t):
        r[j][c - 1] = 1
# print(*r,sep='\n')

ans = 0
for i in range(len(r)):
    ans = max(ans, sum(r[i]))
print(ans)


# 補足
# チャンネル数4の場合以下のような配列ができる
# 1行でとある時間のチャンネル状態(1: 録画する, 0: 録画しない)がつく
#[0, 0, 0, 0]
#[0, 0, 1, 0]
#[1, 1, 1, 0]  <- この時間で3チャンネル録画が必要
#[1, 1, 0, 0]  <- この時間で2チャンネル録画が必要
#[1, 1, 0, 0]
#[1, 0, 0, 0]
Buggy python submission (verdict: Runtime Error):
n = int(input())
t = [int(input()) for _ in range(n)]

def gcd(a,b):
    if b == 0:
        return a
    return gcd (b, a%b)

#2数の積/最大公約数=最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

ans = lcm(t[0],t[1])
for i in range(1, n-1):
    ans = lcm(ans,t[i+1])
print(ans)

Fixed submission:
n = int(input())
t = [int(input()) for _ in range(n)]

def gcd(a,b):
    if b == 0:
        return a
    return gcd (b, a%b)

#2数の積/最大公約数=最小公倍数
def lcm(a,b):
    return a*b//gcd(a,b)

if n == 1:
    print(t[0])
    exit(0)
ans = lcm(t[0], t[1])
for i in range(1, n-1):
    ans = lcm(ans, t[i+1])
print(ans)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = map(int, input().split())
c = [0]*9

for i in a:
    col = i//400
    if 4800<= i:
        c[8] += 1
    else:
        c[col] = 1
print(max(1,sum(c[:8])),sum(c))

Fixed submission:
n = int(input())
a = map(int, input().split())
c = [0]*9

for i in a:
    col = i//400
    if 3200 <= i:
        c[8] += 1
    else:
        c[col] = 1
print(max(1,sum(c[:8])),sum(c))
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n,k=map(int,input().split())
l=list(map(int,input().split()))
d=defaultdict(int)
for i in range(n):
    d[i+1]=l[i]
visited=set()
l=[]
i=1
while True:
    l.append(i)
    if i not in visited:
        visited.add(i)
    else:
        break
    i=d[i]
first=l.index(l[-1])
if k<first:
    print(l[k])
else:
    k=(k-first)%((len(l)-1)-first)
    k+=first
    print(l[k])

Fixed submission:
s=input()
t=input()
if len(t)==len(s)+1 and t[0:len(s)]==s:
    print("Yes")
else:
    print("No")

Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n,k=map(int,input().split())
l=list(map(int,input().split()))
d=defaultdict(int)
for i in range(n):
    d[i+1]=l[i]
visited=set()
l=[]
i=1
while True:
    l.append(i)
    if i not in visited:
        visited.add(i)
    else:
        break
    i=d[i]
first=l.index(l[-1])

k=(len(l)-first)%((len(l)-1)-first)
k+=first
if k<first:
    print(l[k])
else:
    print(l[k-1])

Fixed submission:
s=input()
t=input()
if len(t)==len(s)+1 and t[0:len(s)]==s:
    print("Yes")
else:
    print("No")
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
n,k=map(int,input().split())
l=list(map(int,input().split()))
d=defaultdict(set)
def dfsutil(s,a):
    visited[s]=True
    for i in d[s]:
        if visited[i]==False:
            return dfsutil(i,a+1)
    return a,s,i
def dfsutil2(s,k,a):
    visited[s]=True
    if a==k:
        return s
    for i in d[s]:
        if visited[i]==False:
            return dfsutil2(i,k,a+1)
    
visited=defaultdict(bool)

for i in range(len(l)):
    d[i+1].add(l[i])
c=dfsutil(1,1)
# print(c)
if c[1] in d[c[1]]:
    if k>=c[0]:
        print(c[1])
    else:
        visited=defaultdict(bool)
        print(dfsutil2(1,k,0))   
else:
    if k<=c[0]:
        print(dfsutil2(1,k,0))
    if k>c[0]:
        visited=defaultdict(bool)
        c1=dfsutil(c[2],1)
        if c[2]!=1:
            
            k=k-(c[0]-c1[0])
            
        # visited=defaultdict(bool)
        # print(c)
        # print(c1)
        # print(k)
        k=k%c1[0]
        # print(k)
        # print(c1)
        # print(c1)
        
        # print(k)
        visited=defaultdict(bool)
        if k==0:
            print(c[2])
        else:
            print(dfsutil2(c[2],k,0))
        
    


Fixed submission:
from collections import defaultdict
n,k=map(int,input().split())
l=list(map(int,input().split()))
d=defaultdict(int)
for i in range(n):
    d[i+1]=l[i]
visited=set()
l=[]
i=1
while True:
    l.append(i)
    if i not in visited:
        visited.add(i)
    else:
        break
    i=d[i]
first=l.index(l[-1])
if k<first:
    print(l[k])
else:
    k=(k-first)%((len(l)-1)-first)
    k+=first
    print(l[k])
Buggy python submission (verdict: Runtime Error):
a=int(input())
s=int(input())
if a<3200:
  print("red")
else:
  print(s)

Fixed submission:
a=int(input())
s=input()
if a<3200:
  print("red")
else:
  print(s)
Buggy python submission (verdict: Time Limit Exceeded):
def recur(n,w):
    if n==0 or w==0:
        return 0
    elif (n,w) in dp:
        return dp[(n,w)]
    elif l[n-1][0]<=w:
        k=max(recur(n-1,w-l[n-1][0])+l[n-1][1],recur(n-1,w))
        dp[(n,w)]=k
        return k
    else:
        k=recur(n-1,w)
        dp[(n,w)]=k
        return k
n,w=map(int,input().split())
l=[]
for _ in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
dp=dict()
print(recur(n,w))

Fixed submission:
n,w=map(int,input().split())
l=[]
for _ in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
dp=[[0 for i in range(w+1)]for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,w+1):
        if l[i-1][0]<=j:
            
            dp[i][j]=max(dp[i-1][j],dp[i-1][j-l[i-1][0]]+l[i-1][1])
        else:
            dp[i][j]=dp[i-1][j]
# print(dp)
print(dp[-1][-1])
Buggy python submission (verdict: Time Limit Exceeded):
def recur(n,w):
    if n==0 or w==0:
        return 0
    elif (n,w) in dp:
        return dp[(n,w)]
    elif l[n-1][0]<=w:
        k=max(recur(n-1,w-l[n-1][0])+l[n-1][1],recur(n-1,w))
        dp[(n,w)]=k
        return k
    else:
        k=recur(n-1,w)
        dp[(n,w)]=k
        return k
n,w=map(int,input().split())
l=[]
for _ in range(n):
    a,b=map(int,input().split())
    l.append((a,b))
dp=dict()
print(recur(n,w))
    

Fixed submission:
n,w=map(int,input().split())
l=[]
weight=[0]
value=[0]

for _ in range(n):
    a,b=map(int,input().split())
    value.append(b)
    weight.append(a)
maxvalue=sum(value)
dp=[[10**10 for i in range(maxvalue+1)]for i in range(n+1)]
for i in range(n+1):
    dp[i][0]=0
for i in range(1,n+1):
    for j in range(1,maxvalue+1):
        if value[i]<=j:
            
            dp[i][j]=min(dp[i-1][j],dp[i-1][j-value[i]]+weight[i])
        else:
            dp[i][j]=dp[i-1][j]
for i in range(maxvalue+1):
    if dp[-1][i]<=w:
        ans=i
print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import deque
n, m, k = map(int,input().split())
tmpA = list(map(int,input().split()))
tmpB = list(map(int,input().split()))
A = [tmpA[0]]
B = [tmpB[0]]
for i in range(1, n):
    tmp = A[i-1] + tmpA[i]
    if tmp > k:
        break
    else:
        A.append(tmp)
for i in range(1, m):
    tmp = B[i-1] + tmpB[i]
    if tmp > k:
        break
    else:
        B.append(tmp)

if len(A) == 1 and len(B) == 1:
    if A[0] > k:
        A.pop()
    if B[0] > k:
        B.pop()
    print(len(A) + len(B))
elif len(A) == 1:
    if A[0] > k:
        print(len(B))
    else:
        while True:
            if A[0] + B[-1] <= k:
                break
            if A[0] > B[-1]:
                A.pop()
            else:
                B.pop()
        print(len(A) + len(B))
elif len(B) == 1:
    if B[0] > k:
        print(len(A))
    else:
        while True:
            if B[0] + A[-1] <= k:
                break
            if B[0] > A[-1]:
                B.pop()
            else:
                A.pop()
        print(len(A) + len(B))
else:
    while True:
        if A[-1] + B[-1] <= k:
            break
        if A[-1] > B[-1]:
            A.pop()
        else:
            B.pop()
    print(len(A) + len(B))



Fixed submission:
def is_ok(index, key):
    return B[index] <= key

def upper_bound(key): 
    ng = len(B)
    ok = -1

    while abs(ok - ng) > 1:
        mid = (ok + ng) // 2
        if is_ok(mid, key):
            ok = mid
        else:
            ng = mid
    
    return ok 

n, m, k = map(int, input().split())
tmpA = list(map(int, input().split()))
tmpB = list(map(int, input().split()))
A = [0]
B = [0]
# 読むのにかかる時間の累計和のリスト
if A:
    for i in range(n):
        tmp = A[i] + tmpA[i]
        if tmp > k:
            break
        else:
            A.append(tmp)
if B:
    for i in range(m):
        tmp = B[i] + tmpB[i]
        if tmp > k:
            break
        else:
            B.append(tmp)

answer = 0
for i in range(len(A)):
    key = k - A[i]
    answer = max(answer, upper_bound(key) + i)

print(answer)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
# 題意は「1~Nの値iにおいて、Nまでにあるiの倍数の総和を求めよ」ということなので
sum = 0
for i in range(1, N+1):
    k = N // i # k = iの倍数の項数
    sum += int(i * k * (k+1) / 2)
print(sum)


Fixed submission:
N = int(input())
# 題意は「1~Nの値iにおいて、Nまでにあるiの倍数の総和を求めよ」ということなので
sum = 0
for i in range(1, N+1):
    k = N // i # k = iの倍数の項数
    sum += int(i * k * (k+1) / 2)
print(sum)
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
A = list(map(int, input().split()))
Q = int(input())
for _ in range(Q):
    b, c = map(int, input().split())
    for i,v in enumerate(A):
        if v == b:
            A[i] = c
    print(sum(A))

Fixed submission:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
d = defaultdict(int)
for key in A:
    d[key] += 1
d[sum] = sum(A)

Q = int(input())
for _ in range(Q):
    b, c = map(int, input().split())
    change_sum = d[b] * (c-b)
    d[sum] += change_sum
    d[c] += d[b]
    d[b] = 0
    print(d[sum])
Buggy python submission (verdict: Runtime Error):
a,b=int(input().split())

print(a*b)

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

print(a*b)

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

print(a*b)

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

print(a*b)
Buggy python submission (verdict: Time Limit Exceeded):
N =int(input())
A = list(map(int,input().split()))

pair_count = 0

for i in range(N):
    for j in range(i+1,N):
        if abs(i-j) == A[i]+A[j]:
            pair_count+=1

print(pair_count)

Fixed submission:
'''
i<j としたとき求めたいのは
i + Ai = j - Aj の組み合わせの数
そこで各々の Li = i + Ai, Ri = i - Aiを計算し辞書型で保持しておく
'''
from collections import defaultdict

N =int(input())
A = list(map(int,input().split()))
Li = defaultdict(int)
Ri = defaultdict(int)
for i,a in enumerate(A,start=1):
    Li[i+a] += 1
    Ri[i-a] += 1

ans = 0
for k,v in Li.items():
    if k in Ri:
        ans += Li[k]*Ri[k]

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter
from itertools import combinations as cmb

N = int(input())
S = input()
ans = 0
if N >= 3:    
    for idx in list(cmb(range(N), 3)):
        a,b,c = idx[0],idx[1],idx[2]
        if b-a != c-b and S[a] != S[b] and S[a] != S[c] and S[b] != S[c]:
            ans += 1

print(ans)

Fixed submission:
N = int(input())
S = input()

if N<4:
    print(0)
else:
    a = [0] * N
    R, G, B = 0, 0, 0
    for i in range(N):
        if S[i] == "R":
            a[i] = 1
            R += 1
        if S[i] == "G":
            a[i] = 2
            G += 1
        if S[i] == "B":
            a[i] = 4
            B += 1

    rgb = R * G * B
    cnt = 0
    for i in range(N-2):
        for d in range(1, (N-i-1) // 2+1):
            if a[i] + a[i+d] + a[i+2*d] == 7:
                cnt += 1

    print(rgb -cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N = int(input())
A = list(map(int,input().split()))

count_a = Counter(A)
ans_list = [None] * (N+1)
for i in range(N):
    if ans_list[A[i]] != None:
        print(ans_list[A[i]])
        continue
    ans = 0
    count_a[A[i]] -= 1
    for a in count_a.values():
        if a > 1:
            ans += int(a * (a-1) / 2)
    print(ans)
    ans_list[A[i]] = ans
    count_a[A[i]] += 1


Fixed submission:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))

count_a = Counter(A)
ans_list = [0] * (N+1)
for k, v in count_a.items():
    ans_list[k] = int(v * (v-1) / 2)

all_sum = sum(ans_list)
for i in range(N):
    print(all_sum - count_a[A[i]] + 1)

Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter

N = int(input())
A = list(map(int,input().split()))

count_a = Counter(A)

for i in range(N):
    ans = 0
    count_a[A[i]] -= 1
    for a in count_a.values():
        if a > 1:
            ans += int(a * (a-1) / 2)
    print(ans)
    count_a[A[i]] += 1

Fixed submission:
from collections import Counter

N = int(input())
A = list(map(int,input().split()))

count_a = Counter(A)
ans_list = [0] * (N+1)
for k, v in count_a.items():
    ans_list[k] = int(v * (v-1) / 2)

all_sum = sum(ans_list)
for i in range(N):
    print(all_sum - count_a[A[i]] + 1)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
#n, k = map(int,input().split())
n = int(input())
al = list(map(int,input().split()))

ans = 0
for v in itertools.product(range(2),repeat=n):
    money = 1000
    kabu = 0

    for i in range(n):
        if v[i] == 0:
            kabu += money // al[i]
            money = money % al[i]
        elif v[i] == 1:
            money += kabu * al[i]
            kabu = 0
        else:
            continue
    ans = max(ans, money)
print(ans)


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

kabu = 0
money = 1000
for i in range(n-1):
    if al[i] < al[i+1]:
        # 全部売る
        money += kabu * al[i]
        kabu = 0
        # 全部買う
        kabu += money // al[i]
        money = money % al[i]
    else:
        # 全部売る
        money += kabu * al[i]
        kabu = 0

print(money+ kabu*al[-1])

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

ans = 0
for v in itertools.product(range(3),repeat=n):
    money = 1000
    kabu = 0

    for i in range(n):
        if v[i] == 0:
            kabu += money // al[i]
            money = money % al[i]
        elif v[i] == 1:
            money += kabu * al[i]
            kabu = 0
        else:
            continue
    ans = max(ans, money)
print(ans)

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

kabu = 0
money = 1000
for i in range(n-1):
    if al[i] < al[i+1]:
        # 全部売る
        money += kabu * al[i]
        kabu = 0
        # 全部買う
        kabu += money // al[i]
        money = money % al[i]
    else:
        # 全部売る
        money += kabu * al[i]
        kabu = 0

print(money+ kabu*al[-1])