Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
for i in range(m//n, 0, -1):
  if m%i==0:
    break
print(i)

Fixed submission:
def solve():
  n, m = map(int, input().split())
  for i in range(m//n, 0, -1):
    if m%i==0:
      break
  print(i)

if __name__=='__main__':
  solve()
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
import math
def solve():
    a, b, c, d = map(int, input().split())
    # 自明
    if d < b or a < b:
        return 'No'
    if c > b:
        return 'Yes'
    a %= b
    if a > c:
        return 'No'
    if d-b == 0:
        return 'Yes'
    cache = set([a])
    while True:
        t = ((c-a)//(d-b)+1)*(d-b)+a
        if c < t < b:
            return 'No'
        a = t % b
        if a in cache:
            return 'Yes'
        else:
            cache.add(a)

T = int(input())
for _ in range(T):
    print(solve())

Fixed submission:
#!/usr/bin/env python
from fractions import gcd

def ng(a, b, c, add):
    return 0 < (b-a)%add < (b-c)

def solve():
    a, b, c, d = map(int, input().split())
    # 自明
    if d < b or a < b:
        return 'No'
    if c > b:
        return 'Yes'
    a %= b
    if a > c:
        return 'No'

    if d-b == 0:
        return 'Yes'

    if gcd(b, d-b) < b-c:
        return 'No'
    else:
        return 'Yes'
    # if ng(a, b, c, d-b):
    #     return 'No'

    # # さんざんまわしたらアウトになる
    # t = (d-b)
    # if ng(a, b, c, :
    #     return 'No'
    
    # return 'Yes' 
    
T = int(input())
for _ in range(T):
    print(solve())

Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
def solve():
    a, b, c, d = map(int, input().split())
    if a < b or d < b:
        return 'No'
    cache = set()
    while True:
        a %= b
        if c < a < d:
            return 'No'
        a += (d - b)
        if a in cache:
            return 'Yes'
        cache.add(a)

T = int(input())
for _ in range(T):
    print(solve())

Fixed submission:
#!/usr/bin/env python
from fractions import gcd

def ng(a, b, c, add):
    return 0 < (b-a)%add < (b-c)

def solve():
    a, b, c, d = map(int, input().split())
    # 自明
    if d < b or a < b:
        return 'No'
    if c > b:
        return 'Yes'
    a %= b
    if a > c:
        return 'No'

    if d-b == 0:
        return 'Yes'

    if gcd(b, d-b) < b-c:
        return 'No'
    else:
        return 'Yes'
    # if ng(a, b, c, d-b):
    #     return 'No'

    # # さんざんまわしたらアウトになる
    # t = (d-b)
    # if ng(a, b, c, :
    #     return 'No'
    
    # return 'Yes' 
    
T = int(input())
for _ in range(T):
    print(solve())
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
n = int(input())
s = input()
ans = float('inf')
for i in range(n):
    if i==0:
        cnt = s[1:].count('E')
    elif i==n-1:
        cnt = s[:n-2].count('W')
    else:
        cnt = s[i+1:].count('E') + s[:i-1].count('W')
    ans = min(ans, cnt)
print(ans)


Fixed submission:
#!/usr/bin/env python
n = int(input())
s = input()
ans = float('inf')
E_total = s.count('E')
W_total = s.count('W')
cnt = {'E': 0, 'W': 0}
for i in range(n):
    turn = cnt['W'] + (E_total - cnt['E'])
    if s[i] == 'E':
        turn -= 1
    ans = min(ans, turn)
    cnt[s[i]] += 1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python


class UnionFind:
    def __init__(self, size):
        self.table = list(range(size))

    def find(self, x):
        return self.table[x]

    def union(self, x, y):
        x1 = self.find(x)
        y1 = self.find(y)
        if x1 == y1:
            return False
        for i in range(len(self.table)):
            if self.table[i] == y1:
                self.table[i] = x1
        return True


n, m = map(int, input().split())
ps = list(map(int, input().split()))
uf = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    uf.union(x - 1, y - 1)
print(sum([uf.find(i) == uf.find(p - 1) for i, p in enumerate(ps)]))


Fixed submission:
#!/usr/bin/env python


class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same(self, x, y):
        return self.find(x) == self.find(y)


n, m = map(int, input().split())
ps = list(map(int, input().split()))
uf = UnionFind(n + 1)
for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x, y)
print(sum([uf.same(i + 1, p) for i, p in enumerate(ps)]))
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
import numpy as np
N = int(input())
alphabets = list('abcdefghijklmnopqrstuvwxyz')
A = np.zeros((N, N))
for i in range(N):
    for j, c in enumerate(input()):
        A[i,j] = alphabets.index(c)

B = np.concatenate([A, A], axis=0)
B = np.concatenate([B, B], axis=1)
cnt = 0
for i in range(N):
    for j in range(N):
        C = B[i:i+N, j:j+N]
        if (C==C.T).all():
            cnt += 1
print(cnt)

Fixed submission:
#!/usr/bin/env python
import numpy as np
N = int(input())
alphabets = list('abcdefghijklmnopqrstuvwxyz')
A = np.zeros((N, N), dtype=int)
for i in range(N):
    for j, c in enumerate(input()):
        A[i,j] = alphabets.index(c)

B = np.concatenate([A, A], axis=0)
cnt = 0
for i in range(N):
    C = B[i:i+N, :]
    if (C==C.T).all():
        cnt += 1
print(cnt*N)

Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python
import numpy as np
N = int(input())
alphabets = 'abcdefghijklmnopqrstuvwxyz'
A = np.zeros((N, N))
for i in range(N):
    for j, c in enumerate(input()):
        A[i,j] = alphabets.index(c)

cnt = 0
for i in range(N):
    for j in range(N):
        B = np.roll(A, (i, j), (0, 1))
        if (B==B.T).all():
            cnt += 1
print(cnt)

Fixed submission:
#!/usr/bin/env python
import numpy as np
N = int(input())
alphabets = list('abcdefghijklmnopqrstuvwxyz')
A = np.zeros((N, N), dtype=int)
for i in range(N):
    for j, c in enumerate(input()):
        A[i,j] = alphabets.index(c)

B = np.concatenate([A, A], axis=0)
cnt = 0
for i in range(N):
    C = B[i:i+N, :]
    if (C==C.T).all():
        cnt += 1
print(cnt*N)
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
import numpy as np
N = int(input())
X = np.array(list(map(int, input().split())))
idx = np.ones(N, dtype=bool)
for i in range(N):
    idx[i] = False
    print(int(np.median(X[idx])))
    idx[i] = True


Fixed submission:
#!/usr/bin/env python
import numpy as np
N = int(input())
X = np.array(list(map(int, input().split())))
idx = X.argsort()
low = idx[N//2-1]
high = idx[N//2]

res = np.zeros(N, dtype=int)
res[idx[:N//2]] = X[high]
res[idx[N//2:]] = X[low]

for i in range(N):
    print(res[i])
Buggy python submission (verdict: Runtime Error):
a, b = map(int, input().split())
cnt = 0
for i in range(a, b+1):
  if i==''.join(reversed(i)):
    cnt+=1
print(cnt)

Fixed submission:
a, b = map(int, input().split())
cnt = 0
for i in range(a, b+1):
  if str(i)==''.join(reversed(str(i))):
    cnt+=1
print(cnt)
Buggy python submission (verdict: Runtime Error):
n = int(input())
as = map(int, input().split())
alice = []
bob = []
for i, a in enumerate(as):
    if i%2==0:
        alice.append(a)
    else:
        bob.append(a)
print(sum(alice)-sum(bob))

Fixed submission:
n = int(input())
alist = map(int, input().split())
alice = []
bob = []
for i, a in enumerate(sorted(alist, reverse=True)):
    if i % 2 == 0:
        alice.append(a)
    else:
        bob.append(a)
print(sum(alice) - sum(bob))
Buggy python submission (verdict: Runtime Error):
def main():
    arr = []
    for i in range(3):
        arr.append(map(int, input().split()))
    b1 = arr[0][0] - arr[0][1]
    b2 = arr[0][1] - arr[0][2]
    a1 = arr[1][0] - arr[0][0]
    a2 = arr[2][0] - arr[1][0]
    for i in range(3):
        if arr[i][0] - arr[i][1] != b1 or arr[i][1] - arr[i][2] != b2 or arr[1][i] - arr[0][i] != a1 or arr[2][i] - \
                arr[1][i] != a2:
            print("No")
            return
    print("Yes")

if __name__ == '__main__':
    main()


Fixed submission:
def main():
    arr = []
    for i in range(3):
        arr.append(list(map(int, input().split())))
    b1 = arr[0][0] - arr[0][1]
    b2 = arr[0][1] - arr[0][2]
    a1 = arr[1][0] - arr[0][0]
    a2 = arr[2][0] - arr[1][0]
    for i in range(3):
        if arr[i][0] - arr[i][1] != b1 or arr[i][1] - arr[i][2] != b2 or arr[1][i] - arr[0][i] != a1 or arr[2][i] - \
                arr[1][i] != a2:
            print("No")
            return
    print("Yes")

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from collections import deque

def main():
    N, M = map(int, input().split())
    link = [[] for _ in range(N+1)]
    value = [0 for _ in range(N+1)]

    for _ in range(M):
        l, r, d = map(int, input().split())
        link[l].append((r, d))
        link[r].append((l, -d))

    searched = set()
    q = deque()
    for u in range(N+1):
        if u in searched:
            continue
        q.append(u)
        searched.add(u)
        value[u] = 0

        # search
        while q:
            x = q.popleft()
            for y, d in link[x]:
                if y not in searched:
                    value[y] = value[x] + d
                    q.append(y)
                    searched.add(y)

    # verify
    for x in range(N+1):
        for y, d in link[x]:
            if value[y] != value[x] + d:
                print('No')
                return
    else:
        print('Yes')

if __name__ == '__main__':
    main()

Fixed submission:
x = int(input())
a = int(input())
b = int(input())
print((x-a)%b)

Buggy python submission (verdict: Runtime Error):
N, M = map(int, input().split())
G = [[] for _ in range(N+1)]

# weighted graph
for _ in range(M):
    l, r, d = map(int, input().split())
    G[l].append((r, d))
    G[r].append((l, -d))

cache = set(range(1, N+1))

# depth first search
def dfs(graph, start, visited=None):
    global cache  # for checking disconnected
    visited = visited or {}
    visited[start[0]] = start[1]
    cache.remove(start[0])
    for nxt, v in graph[start[0]]:
        nxt_value = start[1] + v
        if nxt in visited:
            if nxt_value != visited[nxt]:
                return False
            continue
        return dfs(graph, (nxt, nxt_value), visited)
    return True

# while len(cache)>0:
#     if not dfs(G, (list(cache)[0], 0)):
#         print('No')
#         break
# else:
#     print('Yes')

if dfs(G, (0, 0)):
    print('Yes')
else:
    print('No')

Fixed submission:
x = int(input())
a = int(input())
b = int(input())
print((x-a)%b)

Buggy python submission (verdict: Runtime Error):
a, b, c, x = [int(input()) for _ in range(4)]
cnt = 0
for ai in range(a+1):
    for bi in range(b+1):
        for ci in range(c+1):
            if 500*ai + 100*bi + 50*ci == x:
                cnt += 1
print(cnt)


Fixed submission:
x = int(input())
a = int(input())
b = int(input())
print((x-a)%b)
Buggy python submission (verdict: Runtime Error):
a, b, c, x = [int(input()) for _ in range(4)]
cnt = 0
for ai in range(a):
	for bi in range(b):
		for ci in range(c):
        	if 500*ai + 100*bi + 50*ci == x:
				cnt += 1
print(cnt)


Fixed submission:
a, b, c, x = [int(input()) for _ in range(4)]
cnt = 0
for ai in range(0, a+1):
    for bi in range(0, b+1):
        for ci in range(0, c+1):
            if 500*ai + 100*bi + 50*ci == x:
                cnt += 1
print(cnt)

Buggy python submission (verdict: Runtime Error):
a, b, c, x = [int(input()) for _ in range(4)]
cnt = 0
for ai in range(a):
	for bi in range(b):
		for ci in range(c):
        	if 500*ai + 100*bi + 50*ci == x:
            	cnt += 1
print(cnt)

Fixed submission:
a, b, c, x = [int(input()) for _ in range(4)]
cnt = 0
for ai in range(0, a+1):
    for bi in range(0, b+1):
        for ci in range(0, c+1):
            if 500*ai + 100*bi + 50*ci == x:
                cnt += 1
print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)
ans = 0
for ai in a:
    for bi in b:
        if bi <= ai:
            break
        for ci in c:
            if ci <= bi:
                break
            ans += 1
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 bi in b:
    upper = bisect.bisect_left(a, bi)
    lower = n - bisect.bisect_right(c, bi)
    ans += upper * lower
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
#!/usr/bin/env python
n = int(input())
a = list(map(int, input().split()))
ans = float('inf')
for i in range(1, n):
    ans = min(ans, abs(sum(a[:i])-sum(a[i:])))
print(int(ans))

Fixed submission:
#!/usr/bin/env python
n = int(input())
a = list(map(int, input().split()))
total = sum(a)
ans = float('inf')
tmp = 0
for i in range(n):
    tmp += a[i]
    if i==n-1:
        continue
    ans = min(ans, abs(tmp-(total-tmp)))
print(int(ans))
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
a = list(map(int, input().split()))
b = []
for i in range(n):
  b.append(a[i])
  b = list(reversed(b))
print(*b)

Fixed submission:
from collections import deque
n = int(input())
a = list(map(int, input().split()))
b = deque()
last = n%2==0
for i in range(n):
  if last:
    b.append(a[i])
  else:
    b.appendleft(a[i])
  last = not last
print(*b)
Buggy python submission (verdict: Runtime Error):
n = int(input())
a = map(int, input().split())
print(max(a)-min(a))

Fixed submission:
n = int(input())
a = list(map(int, input().split()))
print(max(a)-min(a))
Buggy python submission (verdict: Runtime Error):
g = [0,2,0,1,0,1,0,0,1,0,1,0]
x, y = map(int, input().split())
print('Yes' if g[x]==g[y] else 'No')

Fixed submission:
g = [-1,0,2,0,1,0,1,0,0,1,0,1,0]
x, y = map(int, input().split())
print('Yes' if g[x]==g[y] else 'No')

Buggy python submission (verdict: Runtime Error):
group = [0,2,0,1,0,1,0,0,1,0,1,0]
x, y = map(int, input().split())
print('Yes' if group[x]==group[y] else 'No')

Fixed submission:
g = [-1,0,2,0,1,0,1,0,0,1,0,1,0]
x, y = map(int, input().split())
print('Yes' if g[x]==g[y] else 'No')
Buggy python submission (verdict: Runtime Error):
n, m = map(int, input().split())
l = []
l = [0] * n
for _ in range(m):
    a, b = map(int, input().split())  # 1-index
    l[a] += 1
    l[a] -= 1
    l[a-1] += 1
    l[b-1] += 1

for _ in range(n):
    pass

for i in l:
    print(i)
    

Fixed submission:
#!/usr/bin/env python

n, m = map(int, input().split())
l = []
l = [0] * n
for _ in range(m):
    a, b = map(int, input().split())  # 1-index
    l[a-1] += 1
    l[b-1] += 1

for i in l:
    print(i)
Buggy python submission (verdict: Runtime Error):
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)

def solve_small(K):
    if K == 0:
        return [0, 1]
    elif K == 1:
        return [0, 2]

    return [i for i in range(1, K+1)]

def solve(K):
    N = 50
    q = K // N
    r = K %  N

    if q < 10000 || r < 10:
        A = [q+i-r for i in range(N)]
        A[-1] += r + r*N
    else:
        A = [q+i-3*r for i in range(N)]
        A[-3] += r + r*N - 2
        A[-2] += r + r*N - 1
        A[-1] += r + r*N - 0
        A[-1] -= 2*r

    return A

def main():
    K = int(input())

    if K < 50:
        A = solve_small(K)
    else:
        A = solve(K)

    print(len(A))
    print(" ".join(map(str, A)))

if __name__ == "__main__": main()


Fixed submission:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import sys
import re
import math
import collections
import itertools
import functools

DEBUG = True
DEBUG = False

def dbg(*args):
    if DEBUG:
        print("DBG: ", file=sys.stderr, end="")
        print(*args, file=sys.stderr)

def solve_small(K):
    if K == 0:
        return [0, 1]
    elif K == 1:
        return [0, 2]

    return [i for i in range(1, K+1)]

def solve(K):
    N = 50
    q = K // N
    r = K %  N

    A = [q+i for i in range(N)]
    for i in range(r):
        for j in range(N):
            if j == i:
                A[j] += N
            else:
                A[j] -= 1

    return A

def main():
    K = int(input())

    if K < 50:
        A = solve_small(K)
    else:
        A = solve(K)

    print(len(A))
    print(" ".join(map(str, A)))

if __name__ == "__main__": main()
Buggy python submission (verdict: Runtime Error):
def read_input(filename):
    filein = open(filename, 'r')
    D = int(filein.readline())
    C = filein.readline().split()
    C = [int(i) for i in C]
    S = [list(map(int, filein.readline().split())) for x in range(D)]
    T = [int(filein.readline()) for x in range(D)]
    return D, C, S, T


def scoring(S, D, T, C):
    res = []
    last = [0 for _ in range(26)]
    final = 0
    for i in range(D):
        dec = 0
        for j in range(26):
            for loc, val in enumerate(T[:i + 1]):
                if val == j + 1:
                    last[j] = loc + 1
            dec += C[j] * (i - last[j] + 1)
        final += S[i][T[i] - 1] - dec
        res.append(final)
    return res


D, C, S, T = read_input("sample1.in")
res = scoring(S, D, T, C)
for x in res:
    print(x)


Fixed submission:

def read_input():
    D = int(input())
    C = input().split()
    C = [int(i) for i in C]
    S = [list(map(int, input().split())) for _ in range(D)]
    T = [int(input()) for _ in range(D)]
    return D, C, S, T


def scoring(S, D, T, C):
    res = []
    last = [0 for _ in range(26)]
    final = 0
    for i in range(D):
        dec = 0
        for j in range(26):
            for loc, val in enumerate(T[:i + 1]):
                if val == j + 1:
                    last[j] = loc + 1
            dec += C[j] * (i - last[j] + 1)
        final += S[i][T[i] - 1] - dec
        res.append(final)
    return res


D, C, S, T = read_input()
res = scoring(S, D, T, C)
for x in res:
    print(x)
Buggy python submission (verdict: Time Limit Exceeded):
l, r = list(map(int, input().split()))

s = set()
for i in range(l, r+1):
    s.add(i % 2019)
s = list(s)

ans = 2018
for i, x in enumerate(s):
    for y in s[i+1:]:
        tmp = (x * y) % 2019
        if ans > tmp:
            ans = tmp
print(ans)

Fixed submission:
l, r = list(map(int, input().split()))

if r - l > 2018:
    print(0)
else:
    ans = 2018
    for i in range(l, r):
        for j in range(i+1, r+1):
            tmp = (i * j) % 2019
            if ans > tmp:
                ans = tmp
    print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
l, r = list(map(int, input().split()))

ans = 2019
for i in range(l, r):
    for j in range(i+1, r+1):
        tmp = (i * j) % 2019
        if ans > tmp:
            ans = tmp
print(ans)


Fixed submission:
l, r = list(map(int, input().split()))

if r - l > 2018:
    print(0)
else:
    ans = 2018
    for i in range(l, r):
        for j in range(i+1, r+1):
            tmp = (i * j) % 2019
            if ans > tmp:
                ans = tmp
    print(ans)
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

N = int(input())
_A = [*map(int, input().split())]
Q = int(input())
val = [[*map(int, line.split())] for line in open(0)]

A = defaultdict(int)
for _a in _A:
    A[_a] += 1

ans = sum(_A)
for v in val:
    if v[0] in A.keys():
        num = A[v[0]]
        A[v[0]] = 0
        A[v[1]] += num
        ans += (v[1] - v[0]) * num
    print(ans)


Fixed submission:
from collections import defaultdict

N, _A, Q, *val = [[*map(int, line.split())] for line in open(0)]
N = N[0]
Q = Q[0]

A = defaultdict(int)
for _a in _A:
    A[_a] += 1

ans = sum(_A)
for v in val:
    if v[0] in A.keys():
        num = A[v[0]]
        A[v[0]] = 0
        A[v[1]] += num
        ans += (v[1] - v[0]) * num
    print(ans)
Buggy python submission (verdict: Runtime Error):
S = input()
  
print("ARC" if S == "ABC else "ABC")
      

Fixed submission:
S = input()
  
print("ARC" if S == "ABC" else "ABC")
Buggy python submission (verdict: Runtime Error):
X = int(input())

go = [i**5 for i in range(1000)]


def foo():
    for i in range(1000):
        for j in range(i, 1000):
            if go[i] - go[j] == X:
                return i, j
        for j in range(1000):
            if go[i] + go[j] == X:
                return i, -j


A, B = foo()
print(A, B)


Fixed submission:
X = int(input())

R = 3000
go = [i**5 for i in range(R)]


def foo():
    for i in range(R):
        for j in range(R):
            if go[i] - go[j] == X:
                return i, j
        for j in range(i, R):
            if go[i] + go[j] == X:
                return i, -j

    return 0, 0


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

AI = sorted([(a, i) for i, a in enumerate(A)])

dic = list()
tmp = 0
for i, (a, pos) in enumerate(AI):
    if a > 2 * 10**5:
        break
    if tmp != a:
        tmp = a
        dic.append((a, i))

nums = [a for (a, i) in dic]
inds = [i for (a, i) in dic]
inds.append(N)
L = len(dic)


def check(p1, p2):
    # print(p1, p2)
    sumsum = nums[p1] + nums[p2]
    ret = 0
    for i in range(inds[p1], inds[p1+1]):
        for j in range(inds[p2], inds[p2+1]):
            if sumsum == abs(AI[i][1] - AI[j][1]):
                ret += 1
    # print("return ", ret)
    return ret // 2 if p1 == p2 else ret


# print(dic)
# print(nums)
# print(inds)

ans = 0
for i in range(L):
    for j in range(i, L):
        if nums[i] + nums[j] > 2 * 10**5:
            continue
        ans += check(i, j)

print(ans)


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

L = {}
R = {}
for i, a in enumerate(A):
    x = i + 1 + a
    L[x] = L[x] + 1 if x in L else 1

    x = i + 1 - a
    R[x] = R[x] + 1 if x in R else 1

# print(L, R)

ans = 0
for x in L.keys():
    ans += L[x] * (R[x] if x in R else 0)

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):
    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()))

L = {}
R = {}
for i, a in enumerate(A):
    x = i + 1 + a
    L[x] = L[x] + 1 if x in L else 1

    x = i + 1 - a
    R[x] = R[x] + 1 if x in R else 1

# print(L, R)

ans = 0
for x in L.keys():
    ans += L[x] * (R[x] if x in R else 0)

print(ans)