Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
from operator import mul
from functools import reduce

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

def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n-r, -1))
    under = reduce(mul, range(1, r+1))
    return over // under

mod = 10**9+7

ans = (pow(2, n, mod) -1 - cmb(n, a) % mod - cmb(n, b) % mod) % mod

print(ans)

Fixed submission:
def modComb(n, r, mod):
    nume = 1
    deno = 1
    for i in range(r):
        nume = nume*(n-i) % mod
        deno = deno*(i+1) % mod
    return nume*pow(deno, mod-2, mod) % mod
 
n, a, b = map(int, input().split())

mod = 10**9+7

ans = (pow(2, n, mod) -1 - modComb(n, a, mod)
       - modComb(n, b, mod)) % mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from operator import mul
from functools import reduce

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

def cmb(n, r):
    r = min(n-r, r)
    if r == 0:
        return 1
    over = reduce(mul, range(n, n-r, -1))
    under = reduce(mul, range(1, r+1))
    return over // under

mod = 10**9+7

ans = ((1 << n) % mod -1 - cmb(n, a) % mod - cmb(n, b) % mod) % mod

print(ans)


Fixed submission:
def modComb(n, r, mod):
    nume = 1
    deno = 1
    for i in range(r):
        nume = nume*(n-i) % mod
        deno = deno*(i+1) % mod
    return nume*pow(deno, mod-2, mod) % mod
 
n, a, b = map(int, input().split())

mod = 10**9+7

ans = (pow(2, n, mod) -1 - modComb(n, a, mod)
       - modComb(n, b, mod)) % mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
from operator import mul
from functools import reduce

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

def cmb(n, r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

mod = 10**9+7

ans = (2**n -1 - cmb(n, a) - cmb(n, b))%mod

print(ans)

Fixed submission:
def modComb(n, r, mod):
    nume = 1
    deno = 1
    for i in range(r):
        nume = nume*(n-i) % mod
        deno = deno*(i+1) % mod
    return nume*pow(deno, mod-2, mod) % mod
 
n, a, b = map(int, input().split())

mod = 10**9+7

ans = (pow(2, n, mod) -1 - modComb(n, a, mod)
       - modComb(n, b, mod)) % mod

print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import math
n, a, b = map(int, input().split())

aa = math.factorial(n)/math.factorial(n-a)/math.factorial(a)
bb = math.factorial(n)/math.factorial(n-b)/math.factorial(b)

ans = int(((1 << n) - 1 - aa - bb) % (10**9+7))
print(ans)

Fixed submission:
def modComb(n, r, mod):
    nume = 1
    deno = 1
    for i in range(r):
        nume = nume*(n-i) % mod
        deno = deno*(i+1) % mod
    return nume*pow(deno, mod-2, mod) % mod
 
n, a, b = map(int, input().split())

mod = 10**9+7

ans = (pow(2, n, mod) -1 - modComb(n, a, mod)
       - modComb(n, b, mod)) % mod

print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
dic = dict()

for i in range(n):
    s = input()
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

# print(dic)
# dic2 = sorted(dic.items(), key=lambda x:x[1])
# print(max(dic.values()))
# print(max(dic, key=dic.get))
#
# print(dic.items())

ans = []
for kv in dic.items():
    if kv[1] == max(dic.values()):
        ans.append(kv[0])

ans = sorted(ans)
for a in ans:
    print(a)

Fixed submission:
n = int(input())
dic = dict()

for i in range(n):
    s = input()
    if s in dic:
        dic[s] += 1
    else:
        dic[s] = 1

ans = []
val = max(dic.values())
for kv in dic.items():
    if kv[1] == val:
        ans.append(kv[0])

ans = sorted(ans)
for a in ans:
    print(a)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n = int(input())


def prime_factorize(n):
    r = []
    while n % 2 == 0:
        r.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.append(n)
    return r


p = prime_factorize(n)
ans = 10**13
pr0 = 1

for i in range(1, len(p)+1):
    for P in itertools.combinations(p, i):
        pr = 1
        for pp in P:
            pr *= pp
        ans = min(ans, pr+n//pr-2)

print(ans)

Fixed submission:
n = int(input())

ans = 10**13
for i in range(1, int(n**0.5//1)+1):
    if n%i == 0:
        ans = min(ans, i+n//i-2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n = int(input())


def prime_factorize(n):
    r = []
    while n % 2 == 0:
        r.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.append(n)
    return r


p = prime_factorize(n)
ans = 10**13
pr0 = 1
for pp in p:
    pr0 *= pp

for i in range(1, len(p)+1):
    for P in itertools.combinations(p, i):
        pr = 1
        for pp in P:
            pr *= pp
        ans = min(ans, pr+pr0//pr-2)

print(ans)

Fixed submission:
n = int(input())

ans = 10**13
for i in range(1, int(n**0.5//1)+1):
    if n%i == 0:
        ans = min(ans, i+n//i-2)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import itertools
n = int(input())


def prime_factorize(n):
    r = []
    while n % 2 == 0:
        r.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            r.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        r.append(n)
    return r


p = prime_factorize(n)
ans = 10**13
pr0 = 1
for pp in p:
    pr0 *= pp

for i in range(1, len(p)+1):
    for P in itertools.combinations(p, i):
        pr = 1
        for pp in P:
            pr *= pp
        ans = min(ans, pr+pr0//pr-2)

print(ans)

Fixed submission:
n = int(input())

ans = 10**13
for i in range(1, int(n**0.5//1)+1):
    if n%i == 0:
        ans = min(ans, i+n//i-2)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
sys.setrecursionlimit(500000)

n, q = map(int, input().split())
ab = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
add = [0]*n
for _ in range(q):
    pp, xx = map(int, input().split())
    add[pp-1] += xx


def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in ab[v]:
        if c == p:
            continue
        dfs(c, v, value)


ans = [0]*n
dfs(0, -1, 0)
print(*ans)


Fixed submission:
import sys
sys.setrecursionlimit(500000)

n, q = map(int, input().split())
ab = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
add = [0]*n
for _ in range(q):
    pp, xx = map(int, input().split())
    add[pp-1] += xx


def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in ab[v]:
        if c == p:
            continue
        dfs(c, v, value)


ans = [0]*n
dfs(0, -1, 0)
print(*ans)

Buggy python submission (verdict: Runtime Error):
n, q = map(int, input().split())
ab = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
p, x = [], []
px = dict()
for _ in range(q):
    pp, xx = map(int, input().split())
    p.append(pp-1)
    x.append(xx)
    px[pp-1] = xx


def dfs(now):
    for i in ab[now]:
        if d[i] == -1:
            d[i] = d[now]+1
            dfs(i)


d = [-1]*n
d[0] = 0
dfs(0)
ans = [0]*n
for i in range(len(p)):
    for j in range(n):
        if d[j] >= d[p[i]]:
            ans[j] += x[i]

print(*ans)

Fixed submission:
import sys
sys.setrecursionlimit(500000)

n, q = map(int, input().split())
ab = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = map(int, input().split())
    ab[a-1].append(b-1)
    ab[b-1].append(a-1)
add = [0]*n
for _ in range(q):
    pp, xx = map(int, input().split())
    add[pp-1] += xx


def dfs(v, p, value):
    value += add[v]
    ans[v] = value
    for c in ab[v]:
        if c == p:
            continue
        dfs(c, v, value)


ans = [0]*n
dfs(0, -1, 0)
print(*ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m, q = map(int, input().split())
lr = []
for _ in range(m):
    lr.append(list(map(int, input().split())))

a = [[0] * n for i in range(n)]
for l, r in lr:
    a[l - 1][r - 1] += 1

# cnt = [[0]*n for i in range(n)]
# for y in range(n):
#     v = 0
#     for x in range(y, -1, -1):
#         v += a[x][y]
#         cnt[x][y] = cnt[x][y - 1] + v

for _ in range(q):
    p, q = map(int, input().split())
    cnt = 0
    for l in range(p, q+1):
        for r in range(p, q+1):
            cnt += a[l-1][r-1]
    print(cnt)

Fixed submission:
n, m, q = map(int, input().split())
lr = []
for _ in range(m):
    lr.append(list(map(int, input().split())))

a = [[0] * n for i in range(n)]
for l, r in lr:
    a[l - 1][r - 1] += 1

cnt = [[0]*n for i in range(n)]
for y in range(n):
    v = 0
    for x in range(y, -1, -1):
        v += a[x][y]
        cnt[x][y] = cnt[x][y - 1] + v

for _ in range(q):
    p, q = map(int, input().split())
    print(cnt[p-1][q-1])
Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
cnt = 0
while N > 0:
    cnt += N % 10
    cnt %= 9
    N //= 10
ans = 'Yes' if cnt % 9 == 0 else 'No'
print(ans)


Fixed submission:
N = input()
cnt = 0
for s in N:
    cnt += int(s)
    cnt %= 9
ans = 'Yes' if cnt % 9 == 0 else 'No'
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N = int(input())
cnt = 0
while N > 0:
    cnt += N % 10
    N //= 10
ans = 'Yes' if cnt % 9 == 0 else 'No'
print(ans)


Fixed submission:
N = input()
cnt = 0
for s in N:
    cnt += int(s)
    cnt %= 9
ans = 'Yes' if cnt % 9 == 0 else 'No'
print(ans)
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')
for i in range(N):
    cnt = 0
    k = 0
    done = set()
    S = []
    while i not in done:
        done.add(i)
        ni = P[i] - 1
        if len(S):
            S.append(S[-1] + C[ni])
        else:
            S.append(C[ni])
        i = ni
    if K <= len(S):
        score = max(S[:K])
    elif S[-1] <= 0:
        score = max(S)
    else:
        score = S[-1] * (K // len(S))
        r = K % len(S)
        score += max(0, max(S[:r]))
    ans = max(ans, score)
print(ans)


Fixed submission:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')
for i in range(N):
    cnt = 0
    k = 0
    done = set()
    S = []
    while i not in done:
        done.add(i)
        ni = P[i] - 1
        if len(S):
            S.append(S[-1] + C[ni])
        else:
            S.append(C[ni])
        i = ni
    if K <= len(S):
        score = max(S[:K])
    elif S[-1] <= 0:
        score = max(S)
    else:
        score1 = S[-1] * ((K // len(S)) - 1)
        score1 += max(S)
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')
for i in range(N):
    score = -float('inf')
    cnt = 0
    k = 0
    while k < K:
        ni = P[i] - 1
        cnt += C[ni]
        score = max(cnt, score)
        i = ni
        k += 1
    ans = max(ans, score)
print(ans)


Fixed submission:
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')
for i in range(N):
    cnt = 0
    k = 0
    done = set()
    S = []
    while i not in done:
        done.add(i)
        ni = P[i] - 1
        if len(S):
            S.append(S[-1] + C[ni])
        else:
            S.append(C[ni])
        i = ni
    if K <= len(S):
        score = max(S[:K])
    elif S[-1] <= 0:
        score = max(S)
    else:
        score1 = S[-1] * ((K // len(S)) - 1)
        score1 += max(S)
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys


def B(T):
    global S, Z, D
    _last = [0] * Z
    cnt = 0
    for d in range(1, D + 1):
        t = T[d]
        _last[t] = d
        up = S[d][t]
        down = sum(C[i] * (d - _last[i]) for i in range(Z))
        cnt += up - down
    return cnt


def checkScore(r):
    global D
    L = last[r]
    rst = 0
    for d in range(1, D + 1):
        down = C[r] * (d - L[d])
        up = S[d][r] if down == 0 else 0
        rst += up - down
    return rst


Z = 26
D = int(input())
C = list(map(int, input().split()))
S = [tuple([0] * Z)]
S += [tuple(map(int, input().split())) for _ in range(D)]
T = [None] + [int(input()) - 1 for _ in range(D)]

M = int(input())
Q = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]


last = [[0] * (D + 1) for _ in range(Z)]
V = [0] * Z
for d in range(1, D + 1):
    t = T[d]
    for p in range(Z):
        last[p][d] = last[p][d - 1]
    last[t][d] = d
for p in range(Z):
    V[p] = checkScore(p)

score = sum(V)

for d, q in Q:
    d += 1

    p = T[d]
    T[d] = q

    for r, L in ((p, last[p]), (q, last[q])):
        for e in range(1, D + 1):
            L[e] = L[e - 1] if r != T[e] else e

    score -= V[p] + V[q]
    V[p] = checkScore(p)
    V[q] = checkScore(q)
    score += V[p] + V[q]
    # print(score == B(T), score, B(T))
    print(B(T))


Fixed submission:
import sys


def B(T):
    global S, Z, D
    _last = [0] * Z
    cnt = 0
    for d in range(1, D + 1):
        t = T[d]
        _last[t] = d
        up = S[d][t]
        down = sum(C[i] * (d - _last[i]) for i in range(Z))
        cnt += up - down
    return cnt


def checkScore(r):
    global D, last
    L = last[r]
    rst = 0
    for d in range(1, D + 1):
        down = C[r] * (d - L[d])
        up = S[d][r] if L[d] == d else 0
        rst += up - down
    return rst


Z = 26
D = int(input())
C = list(map(int, input().split()))
S = [tuple([0] * Z)]
S += [tuple(map(int, input().split())) for _ in range(D)]
T = [None] + [int(input()) - 1 for _ in range(D)]

M = int(input())
Q = [tuple(map(lambda x: int(x) - 1, s.split())) for s in sys.stdin.readlines()]


last = [[0] * (D + 1) for _ in range(Z)]
V = [0] * Z
for d in range(1, D + 1):
    t = T[d]
    for p in range(Z):
        last[p][d] = last[p][d - 1]
    last[t][d] = d
for p in range(Z):
    V[p] = checkScore(p)

score = sum(V)

for d, q in Q:
    d += 1

    p = T[d]
    T[d] = q

    for r, L in ((p, last[p]), (q, last[q])):
        for e in range(1, D + 1):
            L[e] = L[e - 1] if r != T[e] else e

    score -= V[p] + V[q]
    V[p] = checkScore(p)
    V[q] = checkScore(q)
    score += V[p] + V[q]
    # # if M > 10 ** 4:
    #     print(score)
    # else:
    #     print(B(T))
    print(score)
Buggy python submission (verdict: Time Limit Exceeded):
def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


MOD = 10 ** 9 + 7
K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

pow25 = [1] * max(L + 1, K + 1)
pow26 = [1] * max(L + 1, K + 1)
for i in range(max(L, K)):
    pow25[i + 1] = (pow25[i] * 25) % MOD
    pow26[i + 1] = (pow26[i] * 26) % MOD

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow25[n - L] * pow26[L + K - n]) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

print(ans)


Fixed submission:
def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


MOD = 10 ** 9 + 7
K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow(25, n - L, MOD) * pow(26, L + K - n, MOD)) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

print(ans)

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


MOD = 10 ** 9 + 7


def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow(25, n - L, MOD) * pow(26, L + K - n, MOD)) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

print(ans)


Fixed submission:
def prepare(n):
    global MOD
    modFacts = [0] * (n + 1)
    modFacts[0] = 1
    for i in range(n):
        modFacts[i + 1] = (modFacts[i] * (i + 1)) % MOD

    invs = [1] * (n + 1)
    invs[n] = pow(modFacts[n], MOD - 2, MOD)
    for i in range(n, 1, -1):
        invs[i - 1] = (invs[i] * i) % MOD

    return modFacts, invs


MOD = 10 ** 9 + 7
K = int(input())
S = input()
L = len(S)
modFacts, invs = prepare(K + L)

ans = 0
for n in range(L, L + K + 1):
    nonSi = (pow(25, n - L, MOD) * pow(26, L + K - n, MOD)) % MOD
    Si = (modFacts[n - 1] * invs[L - 1] * invs[n - 1 - (L - 1)]) % MOD
    ans += nonSi * Si
    ans %= MOD

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

N = int(input())
A = list(map(int, input().split()))
M = 10 ** 6

B = Counter(A)
Key = list(B.keys())
Key.sort()

table = [1] * (M + 1)
cnt = 0
for k in Key:
    if B[k] == 1:
        if table[k] == 1:
            cnt += 1
    for i in range(M):
        if k * i > M:
            break
        else:
            table[k * i] = 0

print(cnt)


Fixed submission:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
M = 10 ** 6

B = Counter(A)
C = list(B.keys())
C.sort()

table = [1] * (M + 1)
cnt = 0
for c in C:
    if B[c] == 1:
        if table[c] == 1:
            cnt += 1
    for i in range(M):
        if c * i > M:
            break
        else:
            table[c * i] = 0

print(cnt)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import deque


H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
grid = [input() for _ in range(H)]

INF = float('inf')
path = [[INF] * W for _ in range(H)]
# pathD = [[INF] * W for _ in range(H)]
path[x1][y1] = 0
# pathD[x1][y1] = 0

q = deque()
q.append((x1, y1, 0, 0, 0))
D = ((0, 1), (1, 0), (0, -1), (-1, 0))
q_append = q.append
q_appendleft = q.appendleft
while q:
    x, y, d, k, s = q.popleft()
    if k == 0:
        for nd in range(4):
            dx, dy = D[nd]
            nx = x + dx; ny = y + dy
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] >= s + 1:
                path[nx][ny] = s + 1
                q.append((nx, ny, nd, K - 1, s + 1))
    else:
        for nd in range(4):
            dx, dy = D[nd]
            nx = x + dx; ny = y + dy
            ns = s + (d != nd)
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny] >= ns:
                path[nx][ny] = ns
                nk = k - 1 if d == nd else K - 1
                appendQ = q_appendleft if d == nd else q_append
                appendQ((nx, ny, nd, nk, ns))

ans = -1 if path[x2][y2] == INF else path[x2][y2]
print(ans)


Fixed submission:
from collections import deque


H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(lambda x: int(x) - 1, input().split())
grid = [input() for _ in range(H)]

INF = float('inf')
path = [[[(INF, INF)] * 4 for _ in range(W)] for _ in range(H)]

q = deque()
for d in range(4):
    path[x1][y1][d] = (1, 0)
    q.append((x1, y1, d, 1, 0))

D = [(-1, 0), (0, 1), (1, 0), (0, -1)]
while q:
    x, y, d, s, k = q.popleft()
    if k == K:
        for nd in range(4):
            if nd == d:
                dx, dy = D[nd]
                nk = 1
            else:
                dx, dy = 0, 0
                nk = 0
            nx = x + dx; ny = y + dy
            ns = s + 1
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (ns, nk):
                path[nx][ny][nd] = (ns, nk)
                q.append((nx, ny, nd, ns, nk))
    else:
        for nd in range(4):
            if nd == d:
                dx, dy = D[nd]
                nk = k + 1
            else:
                dx, dy = 0, 0
                nk = 0
            nx = x + dx; ny = y + dy
            ns = s + (d != nd)
            if 0 <= nx < H and 0 <= ny < W and grid[nx][ny] == '.' and path[nx][ny][nd] > (ns, nk):
                path[nx][ny][nd] = (ns, nk)
                if ns == s:
                    q.appendleft((nx, ny, nd, ns, nk))
                else:
                    q.append((nx, ny, nd, ns, nk))

ans = INF
for d in range(4):
    ans = min(ans, path[x2][y2][d][0])
ans = -1 if ans == INF else ans
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter


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

R = [None] * (N + 1)
R[N] = Counter()
L = [None] * (N + 1)
L[0] = Counter()

# n < i
# for i in range(N):
#     c = Counter()
#     c[A[i] + i] = 1
#     L[i + 1] = L[i] | c

# n >= i
c = Counter()
for n in range(N - 1, -1, -1):
    R[n] = R[n + 1] | c
    R[n][(n + 1) - A[n]] += 1

ans = 0
for i, Ai in enumerate(A):
    # n < a
    # c0 = i - a
    # l = L[i][c0]

    # n >= a
    c1 = Ai + (i + 1)
    r = R[i + 1][c1]

    ans += r

print(ans)


Fixed submission:
from collections import Counter


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

# R = [None] * (N + 1)
# R[N] = Counter()

R = Counter()
cnt = 0
for n in range(N - 1, 0, -1):
    R[(n + 1) - A[n]] += 1
    c = A[n - 1] + ((n - 1) + 1)
    cnt += R[c]

# ans = 0
# for i, Ai in enumerate(A):
#     # n < a
#     # c0 = i - a
#     # l = L[i][c0]

#     # n >= a
#     c1 = Ai + (i + 1)
#     r = R[i + 1][c1]

#     ans += r

print(cnt)