Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

N, X, Y = list(map(int, input().split(' ')))
X -= 1
Y -= 1
dist_map = {}

def search(origin):
  dist = []
  # X, Yの辺がない場合
  for i in range(N):
    dist.append(abs(origin - i))
  # X, Yの辺がある場合
  if dist[X] < dist[Y]:
    dist[Y] = dist[X] + 1
  elif dist[Y] < dist[X]:
    dist[X] = dist[Y] + 1
  for i in range(N):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  for i in reversed(range(N)):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  #print(*dist)
  return dist


for i in range(N):
  dist_map[i] = search(i)

#print(N)
count = [0 for i in range(N)]
for i in range(N):
  #print('i='+str(i))
  #dist = dist_map[i]
  #print(*dist)
  dist = dist_map[i]
  for dis in dist:
    count[dis] += 1
for i in range(1, N):
  print(count[i]//2)

### FIXED CODE ###

N, X, Y = list(map(int, input().split(' ')))
X -= 1
Y -= 1
dist_map = {}

def search(origin):
  dist = []
  # X, Yの辺がない場合
  for i in range(N):
    dist.append(abs(origin - i))
  # X, Yの辺がある場合
  if dist[X] < dist[Y]:
    dist[Y] = dist[X] + 1
  elif dist[Y] < dist[X]:
    dist[X] = dist[Y] + 1
  for i in range(N):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  for i in reversed(range(N)):
    if i - 1 >= 0:
      dist[i] = min(dist[i], dist[i-1]+1)
    if i + 1 < N:
      dist[i] = min(dist[i], dist[i+1]+1)
  #print(*dist)
  return dist

count = [0 for i in range(N)]
for i in range(N):
  dist = search(i)
  for dis in dist:
    count[dis] += 1

for i in range(1, N):
  print(count[i]//2)
### BUGGY CODE ###

s = input()
q = int(input())
query = []
rev = 0
for i in range(q):
    query.append(list(map(str, input().split())))
for i in range(q):
    if len(query[i]) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if int(query[i][1]) == 1:
                s = query[i][2] + s
            else:
                s = s + query[i][2]
        else:
            if int(query[i][1]) == 2:
                s = query[i][2] + s
            else:
                s = s + query[i][2]
if rev == 1:
    s = s[::-1]
print(s)

### FIXED CODE ###

import sys
input = sys.stdin.readline
s = input().rstrip()
q = int(input())
query = []
rev = 0
for i in range(q):
    query.append(list(map(str, input().split())))
sa = []
sb = []
for i in range(q):
    if len(query[i]) == 1:
        rev = (rev + 1) % 2
    else:
        if rev == 0:
            if query[i][1] == '1':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
        else:
            if query[i][1] == '2':
                sa.append(query[i][2])
            else:
                sb.append(query[i][2])
ssa = ''.join(sa)
ssa = ssa[::-1]
ssb = ''.join(sb)
ss = ssa + s + ssb
if rev == 1:
    ss = ss[::-1]
print(ss)
### BUGGY CODE ###

N, W = map(int, input().split())
wlis, vlis = [0], [0]
for i in range(N):
    w, v = map(int, input().split())
    wlis.append(w)
    vlis.append(v)
dp = [[0]*(W+1) for _ in range(N+2)]
for i in range(1, N+1):
    for j in range(W+1):
        if wlis[i] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wlis[i]]+vlis[i])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
print(dp[N+1][W])

### FIXED CODE ###

N, W = map(int, input().split())
wlis, vlis = [0], [0]
for i in range(N):
    w, v = map(int, input().split())
    wlis.append(w)
    vlis.append(v)
dp = [[0]*(W+1) for _ in range(N+2)]
for i in range(1, N+1):
    for j in range(W+1):
        if wlis[i] <= j:
            dp[i+1][j] = max(dp[i][j], dp[i][j-wlis[i]]+vlis[i])
        dp[i+1][j] = max(dp[i][j], dp[i+1][j])
print(dp[N+1][W])
### BUGGY CODE ###

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

seed = []

while A:
    A = sorted(A)
    wareta = []
    warenai = []

    q = A.pop(0)
    for a in A:
        if a % q == 0:
            wareta.append(a)
        else:
            warenai.append(a)

    if q not in wareta:
        seed.append(q) 

    A = warenai[:]

print(len(seed))

### FIXED CODE ###

from collections import Counter

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

maxA = max(A)
C = Counter(A)

D = {a: 0 for a in A}
for a in A:
  t = 2
  while a * t <= maxA:
      D[a * t] = 1
      t += 1

ans = 0
for a in A:
    if C[a] == 1 and D[a] == 0:
        ans += 1

print(ans)
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
MOD = 10**9+7
for elem in a:
    g *= elem//fractions.gcd(g,elem)
res = sum([g//elem for elem in a])
print(res%MOD)


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
g = 1
res = 0
MOD = 10**9+7
for elem in a:
    tmp = g*elem//fractions.gcd(g,elem)
    res *= tmp//g
    g = tmp
    res += g//elem
print(res%MOD)
### BUGGY CODE ###

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

for i in range(M):
  m = max(A)
  if m == 0:
    break
  A.remove(m)
  A.append(int((m - m % 2) * 0.5))
S = 0
for j in range(N):
  S += A[j]
print(S)

### FIXED CODE ###

import heapq
pq = []

N, M = map(int, input().split())
A = list(map(int, input().split()))
for i in A:
  heapq.heappush(pq, -i)
for i in range(M):
  x = pq[0]
  heapq.heappop(pq)
  heapq.heappush(pq, -((-x)//2))
print(-sum(pq))
### BUGGY CODE ###

from operator import mul
from functools import reduce
import itertools
import copy

N = int(input())

# N = i*jをみつける
# (i, j)


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

def remove_dup_list(tmplist):
    return map(list, set(map(tuple, tmplist)))


prime_list = prime_factorize(N)

if len(prime_list)<=1:
    result = N-1
else:
    result = 10**12


#print(prime_list)
for i in range(len(prime_list)//2):
    # i個抽出
    tmp = list(itertools.combinations(prime_list, i+1))
    tm = remove_dup_list(map(list, tmp))
    #print(tm)
    for _ in tm:
        temp_origin_list = copy.copy(prime_list)
        for item in _:
            temp_origin_list.remove(item)
        result = min(result, reduce(mul, _) + reduce(mul, temp_origin_list) - 2)

print(result)



### FIXED CODE ###

import math
N = int(input())
result = N
for i in range(1, int(math.sqrt(N))+2):
    if N % i == 0:
        result = min(result, i - 1 + N//i - 1)
print(result)
### BUGGY CODE ###

k = int(input())
s = input()
n = len(s)
MOD = 10 ** 9 + 7

ans = 0
comb = 1
for i in range(k+1):
    if i > 0: comb = comb * (n+i-1) * pow(i, MOD-2, MOD) % MOD
    ans = (ans + comb * pow(25, i, MOD) * pow(26, k-i, MOD)) % MOD
print(ans)


### FIXED CODE ###

k = int(input())
s = input()
n = len(s)
MOD = 10 ** 9 + 7

ans = 0
comb = 1
for i in range(k+1):
    if i > 0: comb = comb * (n+i-1) * pow(i, MOD-2, MOD) % MOD
    ans = (ans + comb * pow(25, i, MOD) * pow(26, k-i, MOD)) % MOD
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = input()
q = int(input())
flag = True
for i in range(q):
    qfc = input()
    if qfc[0] == '1':
        if flag:
            flag = False
        else:
            flag = True
    else:
        if qfc[2] == '1':
            if flag:
                s = qfc[4] + s
            else:
                s += qfc[4]
        else:
            if flag:
                s += qfc[4]
            else:
                s = qfc[4] + s
if flag:
    print(s)
else:
    print(s[::-1])


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

s = input()
q = int(input())
flag = True
p = ''
m = ''
for i in range(q):
    qfc = input()
    if qfc[0] == '1':
        if flag:
            flag = False
        else:
            flag = True
    else:
        if qfc[2] == '1':
            if flag:
                p += qfc[4]
            else:
                m += qfc[4]
        else:
            if flag:
                m += qfc[4]
            else:
                p += qfc[4]
if flag:
    print(p[::-1] + s + m)
else:
    print(m[::-1] + s[::-1] + p)
### BUGGY CODE ###

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


N, K = map(int, input().split())
A = list(map(int, input().split()))
if K in A:
    print("POSSIBLE")
    exit()

max_val = max(A)
if max_val < K:
    print("IMPOSSIBLE")
    exit()

gcd_val = A[0]
for a in A[1:]:
    gcd_val = gcd(gcd_val, a)

ans = max_val
while K <= ans:
    if K == ans:
        print("POSSIBLE")
        exit()
    else:
        ans -= gcd_val
print("IMPOSSIBLE")

### FIXED CODE ###

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


N, K = map(int, input().split())
A = list(map(int, input().split()))
if K in A:
    print("POSSIBLE")
    exit()

max_val = max(A)
if max_val < K:
    print("IMPOSSIBLE")
    exit()

gcd_val = A[0]
for a in A[1:]:
    gcd_val = gcd(gcd_val, a)

ans = max_val
while K <= ans:
    if K == ans:
        print("POSSIBLE")
        exit()
    else:
        ans -= gcd_val
print("IMPOSSIBLE")
### BUGGY CODE ###

import numpy as np

n = int(input())
d = list(map(int, input().split()))

a = []
for i in range(n):
    line = [0 for j in range(n)]
    line[i] = 1
    if i + 1 >= n:
        i = -1
    line[i + 1] = 1
    a.append(line)
    d[i] = d[i] * 2

b = np.array(d)

Ainv = np.linalg.inv(a)         # A の逆行列を計算
x = np.dot(Ainv, b) 

# for k in range(n):
#     p = a[k][k]

#     for j in range(k, n + 1):
#         a[k][j] = a[k][j] / p
#     for i in range(n):
#         print(a[i])
#     print("-------------")
#     for i in range(n):
#         if i != k:
#             d = a[i][k]
#             for j in range(k, n + 1):
#                 a[i][j] = a[i][j] - d * a[k][j]
ans = []
for i in range(n):
    ans.append(str(int(x[i])))
print(" ".join(ans))

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
bSum = 0
h = 1
for i in range(n):
    d[i] = d[i] * 2
    bSum = bSum + (d[i] * h)
    h = h * -1
m1 = bSum / 2

ans = [int(m1)]
for i in range(n - 1):
    ans.append(int(d[i] - ans[i]))
print(" ".join(map(str, ans)))
### BUGGY CODE ###

N=int(input())
a=input().split(' ')
s=1
for i in range(N):
    s*=int(a[i])
if 0 in a:
    print(0)
if s<=10**18:
    print(s)
else:
    print("-1")

### FIXED CODE ###

import sys
N=int(input())
a=list(map(int, input().split()))
s=1
# aに0がある場合を省く
if 0 in a:
    print(0)
    sys.exit()
else:
# sが10^18になったら打ち切る
    for i in a:
        if s<10**18:
            s*=i
    if s>10**18:
        print(-1)
        sys.exit()
    print(s)
### BUGGY CODE ###


def main():
    N = int(input())
    C = list(input())
    min_max = N
    #方針:borderの左のWと右側のRの個数を求める
    for border in range(N+1):
        R_red_cnt = 0 
        L_white_cnt = 0
        for j in range(border):#仕切りの左側のWの個数を求める. 
            if C[j] == "W":
                L_white_cnt +=1
        for j in range(border,N):#仕切りの右側のRの個数を求める.
            if C[j] == "R":
                R_red_cnt +=1
        if L_white_cnt > R_red_cnt:#左側のWと右側のRの個数の大きいほうを保存(最小交換回数)
            max = L_white_cnt
        else:
            max = R_red_cnt
        if max < min_max:#今までの仕切りのパターンの中で最も小さい最小回数を保存
            min_max = max
        
    print(min_max)

if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    N = int(input())
    C = list(input())
    R_cnt = C.count("R")#Rの個数を数える
    #方針 RR...RWWW...Wの形になれば良いので
    #RR..WRWR/WWW...RRWW  ・・・/の位置がRの個数番目であれば, そこまでのWの個数分「/」の右側のRと交換すればよい
    cnt = 0
    for i in range(R_cnt):
        if C[i] == "R":
            cnt+=1
    print(R_cnt - cnt)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

import itertools
n = int(input())
K = list(range(1, n + 1))
A = list(map(int, input().split()))
K_A = list(zip(K, A))
C = list(itertools.combinations(K_A, 2))
ans = 0
for c in C:
    if abs(c[0][0] - c[1][0]) == c[0][1] + c[1][1]:
        ans += 1
print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
B = [i + A[i - 1] for i in range(1, n + 1)]
C = Counter(B)
ans = 0
for i in range(1, n + 1):
    x = i - A[i - 1]
    if x in C.keys():
        ans += C[x]
print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(3001):
    for g in range(3001):
        tmp = N - r * R - g * G
        if tmp % B == 0 and tmp // B >= 0:
            ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N // R + 1):
    for g in range((N - R * r) // G + 1):
        tmp = N - r * R - g * G
        if tmp % B == 0:
            ans += 1

print(ans)
### BUGGY CODE ###

n = int(input())
buttons = [input() for i in range(n)]
buttons_int = [int(b) - 1 for b in buttons]
button = 0
count = 0
history_list = []
i = 0
while i < n:
    if button == i:
        button = buttons_int[i]
        count += 1
        if button == 1:
            print(count)
            exit()
        if i in history_list:
            print(-1)
            exit()
        else:
            history_list.append(i)
        i = 0
    else:
        i += 1


### FIXED CODE ###

n = int(input())
buttons = [input() for i in range(n)]
buttons_int = [int(b) - 1 for b in buttons]
button = 0
for count in range(1, n+1):
    button = buttons_int[button]
    if button == 1:
        print(count)
        exit()
print(-1)
### BUGGY CODE ###

from collections import defaultdict
d = defaultdict(int)

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

for el in a:
    d[el] += 1

def s_sum(dd):
    res = 0
    for k,v in dd.items():
        res += k * v
    return res

for ss in bc:
    b = ss[0]
    c = ss[1]

    b_cnt = d[b]
    c_cnt = d[c]
    d[b] = 0
    d[c] += b_cnt
    print(s_sum(d))


### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)

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

#print(bc)

for el in a:
    d[el] += 1

def s_sum(dd):
    res = 0
    for k,v in dd.items():
        res += k * v
    return res

wk = s_sum(d)

for ss in bc:
    b = ss[0]
    c = ss[1]

    b_cnt = d[b]
    c_cnt = d[c]
    d[b] = 0
    d[c] += b_cnt
    wk = wk + b_cnt*c - b_cnt*b
    print(wk)
### BUGGY CODE ###

K, s = map(int, input().split())

ans = 0
for x in range(0, K+1):
    for y in range(0, K+1):
        for z in range(0, K+1):
            if x + y + z == s:
                ans += 1
print(ans)

### FIXED CODE ###

K, s = map(int, input().split())

ans = 0
for x in range(0, K+1):
    for y in range(0, K+1):
        if s - (x + y) <= K and s - (x + y) >= 0 :
            ans += 1
print(ans)
### BUGGY CODE ###

n=int(input())
s=input()
cnt=0
for i in range(n):
  for j in range(i+1,n):
    for k in range(j+1,n):
      if s[i]!=s[j] and s[i]!=s[k] and s[j]!=s[k] and j-i!=k-j:
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
s=input()

r,g,b=s.count('R'),s.count('G'),s.count('B')

cnt=0

for i in range(n):
  d=0
  while 1:
    d+=1
    j=i+d
    k=j+d
    if not k<n:
      break
    if not (s[i]==s[j] or s[j]==s[k] or s[k]==s[i]):
      cnt+=1
print(r*g*b-cnt)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
S = 0

for i in range(1, N+1):
    B[i] = A.count(i)
    S += B[i]*(B[i]-1)//2

for k in range(N):
    print(S-B[A[k]]+1)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = [0]*(N+1)
S = 0

for i in range(N):
    B[A[i]] += 1

for i in range(1, N+1):
    S += B[i]*(B[i]-1)//2

for k in range(N):
    print(S-B[A[k]]+1)
### BUGGY CODE ###

s = str(input())
n = len(s)
ans = ""
for i in range(n):
  if s[i] == "?":
    ans += "D"
  else:
    ans += s[i]

print(ans)

### FIXED CODE ###

s = str(input())
n = len(s)
t= list(s)
ans = ""
for i in range(n):
  if t[i] == "?":
    t[i] = "D"

ans = ''.join(t)

print(ans)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(3000 // R + 1):
    if N - r * R < 0:
        continue
    for g in range(3000 // G + 1):
        tmp = N - r * R - g * G
        if tmp < 0:
            break
        if tmp % B == 0 and tmp // B >= 0:
            ans += 1

print(ans)


### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N // R + 1):
    for g in range((N - R * r) // G + 1):
        tmp = N - r * R - g * G
        if tmp % B == 0:
            ans += 1

print(ans)
### BUGGY CODE ###

n=int(input())
a = list(map(int,input().split()))
mod = 10**9 +7
ans = 0

for i in range(n-1):
    for j in range(i+1,n):
        ans += a[i]*a[j]
print(ans%mod)

### FIXED CODE ###

n=int(input())
a = list(map(int,input().split()))
mod = 10**9 +7
s = 0
ss =0
for i in range(n):
    s += a[i]
    ss += a[i] * a[i]

ans = (s*s - ss)//2
print(ans%mod)
### BUGGY CODE ###

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

def calc(n):
    lst = []
    
    if n%4==1 or n%4==2:lst.append(1)
    else:lst.append(0)
      
    m = 1
    while n//2**m!=0:
        l = n%2**(m+1)
        if l >= 2**m and l%2==0:
            lst.append(1)
        else:lst.append(0)
        m += 1
    return lst

lsta = calc(a-1)
lstb = calc(b)


lsta += [0]*(len(lstb)-len(lsta))

lstab = [(i+j)%2 for i, j in zip(lstb, lsta)]

lstabsum = [lstab[i]*2**i for i in range(len(lstab))]
print(sum(lstabsum))

### FIXED CODE ###

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

def calc(n):
    lst = []
    if n==-1:return '0b0'
    if n%4==1 or n%4==2:lst.append('1')
    else:lst.append('0')
      
    mm = 2
    
    while n//mm != 0:
        l = n%(2*mm)
        if l >= mm and l%2==0:
            lst.append('1')
        else:lst.append('0')
        mm *= 2
    lst.append('0b')
    lst.reverse()
    return ''.join(lst)

lsta = int(calc(a-1),0)
lstb = int(calc(b),0)

print(lsta^lstb)
### BUGGY CODE ###

from collections import Counter # 重複個数のカウント: Counter(num_list)

def main():
    n = int(input())
    num_list = list(map(int, input().split()))

    ans = 0

    cnt_list = Counter(num_list)

    for i in range(n):
        for k, v in cnt_list.items():
            if k == num_list[i]:
                v -= 1
            if v == 1:
                continue
            ans += v * (v-1) // 2
        print(ans)
        ans = 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter # 重複個数のカウント: Counter(num_list)

def main():
    n = int(input())
    num_list = list(map(int, input().split()))

    ans_list = [0] * n
    cnt_list = Counter(num_list)
    for k, v in cnt_list.items():
        if v == 1:
            ans_list[k-1] = 0
            continue
        ans_list[k-1] = v * (v-1) // 2
        
    sum_num = sum(ans_list)

    ans = sum_num

    for i in range(n):
        ans -= ans_list[num_list[i]-1]
        if cnt_list[num_list[i]]-1 != 1:
            ans += (cnt_list[num_list[i]]-1) * (cnt_list[num_list[i]]-2) // 2
        print(ans)
        ans = sum_num

if __name__ == '__main__':
    main()
### BUGGY CODE ###

#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
n,m=map(int,input().split())
d={i:[] for i in range(1,n+1)}
for i in range(m):
	x,y=map(int,input().split())
	d[x].append(y)
	d[y].append(x)


vis=set()

count=0
que=[]
for i in range(1,n+1):
	if i not in vis:
		que=[]
		c=1
		vis.add(i)
		que.append(i)
		while len(que)!=0:
			x=que.pop(0)
			for j in d[x]:
				if j not in vis:
					vis.add(j)
					c+=1
					que.append(j)
		count=max(c,count)

print(count)













































### FIXED CODE ###

#ceilevenoddformula
import math
import bisect
import copy
import time
from collections import Counter
from itertools import combinations
#map(int,input().split())
#int(x) for x in input().split()
n,m=map(int,input().split())
d={i:set() for i in range(1,n+1)}
for i in range(m):
	x,y=map(int,input().split())
	d[x].add(y)
	d[y].add(x)


vis={i:False for i in range(1,n+1)}
for u,v in d.items():
	d[u]=list(v)
count=0
que=[]
for i in range(1,n+1):
	if not vis[i]:
		que=[]
		c=1
		vis[i]=True
		que.append(i)
		while len(que)!=0:
			x=que.pop(0)
			for j in d[x]:
				if not vis[j]:
					vis[j]=True
					c+=1
					que.append(j)
		count=max(c,count)

print(count)
### BUGGY CODE ###

#n,m = map(int,input().split())
#h = list(map(int,input().split()))

#ab = [map(int,input().split()) for _ in range(m)]
#a,b = [list(i) for i in zip(*ab)]

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

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

"""

R=[0]*n
L=[0]*n

for i in range(n):
    R[i]=a[i]+i+1
    L[i]=i+1-a[i]

for i in range(n):
    cnt+=L.count(R[i])

print(cnt)


    

### FIXED CODE ###

#n,m = map(int,input().split())
#h = list(map(int,input().split()))

#ab = [map(int,input().split()) for _ in range(m)]
#a,b = [list(i) for i in zip(*ab)]

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

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

"""

R=dict()
L=dict()

for i in range(n):
    if a[i]+i+1 in R:
        R[a[i]+i+1]+=1
    else:
        R[a[i]+i+1]=1

    if i+1-a[i] in L:
        L[i+1-a[i] ]+=1
    else:
        L[i+1-a[i] ]=1


for i in R:
    if i in L:
        cnt+=R[i]*L[i]

print(cnt)
### BUGGY CODE ###

import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X = INT()

A = []
tmp = 0
for i in range(1, X+1):
    tmp += i
    A.append(tmp)

for i in range(len(A)):
    if X <= A[i]:
        print(i+1)
        break


### FIXED CODE ###

import sys
import re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

X = INT()

A = []
tmp = 0
for i in range(1, X+1):
    tmp += i
    A.append(tmp)
    if tmp >= X:
        print(i)
        break