CodeEff/ECCO huggingface dataset:
# Original solution
import sys
sys.setrecursionlimit(10**9)
from collections import deque


N, M = list(map(int, input().split()))
tree = [[] for i in range(N)]
for i in range(N-1):
  x, y = list(map(int, input().split()))
  tree[x-1].append(y-1)
  tree[y-1].append(x-1)


dp1 = [0] * N
dp2 = [0] * N

def solve(node, parent):
  global dp1
  if dp1[node] > 0:
    return dp1[node]
  else:
    children = tree[node]
    t = 1
    for child in children:
      if child == parent:
        continue
      t *= (solve(child, node) + 1)
      # t %= M
    
    dp1[node] = t
    return t


_ = solve(0, -1)

dp2[0] = dp1[0]
d = deque([])
for child in tree[0]:
  d.append([child, 0])

while d:
  node, parent = d.popleft()
  dp2[node] = (dp2[parent]//(dp1[node]+1) + 1) * dp1[node]
  children = tree[node]
  for child in children:
    if child == parent:
      continue
    
    d.append([child, node])

for ans in dp2:
  print((ans%M))

# Optimized solution
# 参考 -> https://atcoder.jp/contests/dp/submissions/8271798

import itertools
import sys
input = sys.stdin.readline

N, MOD = map(int, input().split())
XY = [list(map(int, input().split())) for i in range(N-1)]
prod = lambda x, y: x*y%MOD

tree = [[] for i in range(N)]
for x, y in XY:
  tree[x-1].append(y-1)
  tree[y-1].append(x-1)

root = 0
parent = [-1] * (N+1)
order = []
stack = [root]
while stack:
  node = stack.pop()
  order.append(node)
  for child in tree[node]:
    if child == parent[node]:
      continue
    parent[child] = node
    stack.append(child)

# dp_down[i] : 頂点iを黒く塗ったときの子側の塗り方
dp_down = [0] * N
for node in order[::-1]: # 葉から根に向かって伝搬させる
  res = 1
  for child in tree[node]:
    res *= dp_down[child] + 1
    res %= MOD
  dp_down[node] = res

# dp_up[i] : 頂点iを黒く塗ったときの親側の塗り方
dp_up = [1] * N
for node in order: # 根から葉に向かって伝搬させる
  par = parent[node]
  arr = [dp_down[c]+1 if c!=par else dp_up[node] for c in tree[node]]
  # それぞれの子(=c)について、自身を根とする下側の部分木を除いた積
  left = [1] + list(itertools.accumulate(arr, prod))[:-1]
  right = list(itertools.accumulate(reversed(arr), prod))[-2::-1] + [1]
  upper_cases = [l*r%MOD for l, r in zip(left, right)]
  for c, res in zip(tree[node], upper_cases):
    if c != par:
      dp_up[c] = res + 1 # (+1 : cより上側が全て白である場合を足し合わせる)

ans = [d*u%MOD for d, u in zip(dp_down, dp_up)]
print(*ans, sep='\n')
# Original solution
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
def dfs(v,p):
    if res_v[v]!=-1:
        return res_v[v]
    size[v]=len(G[v])
    dp[v]=[0]*size[v]
    res=1
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            p_i[v]=i
            continue
        R=dfs(nv,v)
        dp[v][i]=R
        res=res*(R+1)%MOD
    return res
    
def reroot(v,res_p,p):
    if p!=-1:
        dp[v][p_i[v]]=res_p
    for i in range(size[v]):
        ans[v]=ans[v]*(dp[v][i]+1)%MOD
    dp_L=[1]*(size[v]+1)
    dp_R=[1]*(size[v]+1)
    for i in range(size[v]):
        dp_L[i+1]=dp_L[i]*(dp[v][i]+1)%MOD
    for i in reversed(range(size[v])):
        dp_R[i]=dp_R[i+1]*(dp[v][i]+1)%MOD
        
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            continue
        reroot(nv,dp_L[i]*dp_R[i+1]%MOD,v)

N,MOD=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
res_v=[-1]*N
dp=[[] for i in range(N)]
size=[-1]*N
p_i=[-1]*N
dp_L=[[] for i in range(N)]
dp_R=[[] for i in range(N)]
ans=[1]*N

z_root=dfs(0,-1)
res_v[0]=z_root
reroot(0,0,-1)
print(*ans,sep='\n')


# Optimized solution
import sys
sys.setrecursionlimit(10**7)
input=sys.stdin.readline
def dfs(v,p):
    size[v]=len(G[v])
    dp[v]=[0]*size[v]
    res=1
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            p_i[v]=i
            continue
        R=dfs(nv,v)
        dp[v][i]=R
        res=res*(R+1)%MOD
    return res
    
def reroot(v,res_p,p):
    if p!=-1:
        dp[v][p_i[v]]=res_p
    for i in range(size[v]):
        ans[v]=ans[v]*(dp[v][i]+1)%MOD
    dp_L=[1]*(size[v]+1)
    dp_R=[1]*(size[v]+1)
    for i in range(size[v]):
        dp_L[i+1]=dp_L[i]*(dp[v][i]+1)%MOD
    for i in reversed(range(size[v])):
        dp_R[i]=dp_R[i+1]*(dp[v][i]+1)%MOD
        
    for i in range(size[v]):
        nv=G[v][i]
        if nv==p:
            continue
        reroot(nv,dp_L[i]*dp_R[i+1]%MOD,v)

N,MOD=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    x,y=map(lambda x:int(x)-1,input().split())
    G[x].append(y)
    G[y].append(x)
dp=[[] for i in range(N)]
size=[-1]*N
p_i=[-1]*N
dp_L=[[] for i in range(N)]
dp_R=[[] for i in range(N)]
ans=[1]*N

z_root=dfs(0,-1)
reroot(0,0,-1)
print(*ans,sep='\n')
# Original solution
import itertools
while 1:
    n,m,s=list(map(int,input().split()))
    if n==0:break
    dp=[[0 for _ in range(s+2)] for _ in range(n*n+1)]
    dp[0][0]=1
    for i,j in itertools.product(list(range(1,m+1)),list(range(n*n,0,-1))):
        for k in range(i,s+1):
            dp[j][k]=(dp[j][k]+dp[j-1][k-i])%100000
    print((dp[n*n][s]))

# Optimized solution
import itertools
while 1:
    n,m,s=list(map(int,input().split()))
    if n==0:break
    dp=[[0 for _ in range(s+1)] for _ in range(n*n+1)]
    dp[0][0]=1
    for i,j in itertools.product(list(range(1,n*n+1)),list(range(s+1))):
        if j>=i:dp[i][j]+=dp[i-1][j-i]+dp[i][j-i]
        if j-m>=1:dp[i][j]+=100000-dp[i-1][j-m-1]
        dp[i][j]%=100000
    print((dp[n*n][s]))
# Original solution
def main():
    n=int(eval(input()))
    aa=list(map(int,input().split()))
    ll={}
    for i,a in enumerate(aa,1):
        x=i-a
        if x < 1:
            continue
        if x not in ll:
            ll[x]=[i]
        else:
            ll[x].append(i)
    c=0
    for i,a in enumerate(aa,1):
        x=i+a
        if x not in ll:
            continue
        c+=sum(j>i for j in ll[x])
    print(c)
main()

# Optimized solution
def main():
    n=int(eval(input()))
    aa=list(map(int,input().split()))
    ll={}
    c=0
    for i,a in enumerate(aa,1):
        x=i-a
        if x in ll:
            c+=len(ll[x])
        y=i+a
        if y in ll:
            ll[y].append(i)
        else:
            ll[y]=[i]
    print(c)
main()
# Original solution
import sys
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)

N = int(readline().rstrip())
A = list(map(int, readline().split()))

import itertools
pairs = list(itertools.combinations(list(range(0, N)), 2))

ans = 0
for pair in pairs:
    x1, x2 = pair
    if abs(x1 - x2) == A[x1] + A[x2]:
        ans += 1

print(ans)

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

N = int(readline().rstrip())
A = list(map(int, readline().split()))

d1 = {}
d2 = {}
for n in range(1, N+1):
    x1 = n + A[n-1]
    if x1 in d1:
        d1[x1] += 1
    else:
        d1[x1] = 1
    
    x2 = n - A[n-1]
    if x2 in d2:
        d2[x2] += 1
    else:
        d2[x2] = 1

ans = 0
for d in d1:
    if d in d2:
        ans += (d1[d] * d2[d])
print(ans)
# Original solution
from collections import Counter
n = int(eval(input()))
a = list(map(int,input().split()))
L = [0]*n
R = [0]*n
cnt=0
for i in range(n):
    L[i] = i+a[i]
    R[i] = i-a[i]
z1=dict(Counter(L))
z2=dict(Counter(R))
cnt=0
for k1,v1 in list(z1.items()):
    for k2,v2 in list(z2.items()):
        if k1 == k2:
            cnt += v1*v2
print(cnt)

# Optimized solution
from collections import Counter
n = int(eval(input()))
a = list(map(int,input().split()))
L = [0]*n
R = [0]*n
cnt=0
for i in range(n):
    L[i] = i+a[i]
    R[i] = i-a[i]
z1=Counter(L)
z2=Counter(R)
cnt=0
for k1,v1 in list(z1.items()):
    v2 = z2[k1]
    cnt += v1*v2
print(cnt)
# Original solution
from collections import Counter


def main():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    b = []
    c = []
    for i in range(n):
        b.append(a[i] + i + 1)
        c.append(i + 1 - a[i])
    b = list(Counter(b).items())
    c = Counter(c)
    answer = 0
    for i, n in b:
        if i in c:
            answer += n * c[i]
    print(answer)


if __name__ == '__main__':
    main()



# Optimized solution
def main():
    n = int(eval(input()))
    a = list(map(int, input().split()))
    b = []
    c = {}
    answer = 0
    for i in range(n):
        b.append(a[i] + i + 1)
        tmp = -a[i] + i + 1
        if tmp in c:
            c[tmp] += 1
        else:
            c[tmp] = 1
    for i in range(n):
        if b[i] in c:
            answer += c[b[i]]
    print(answer)


if __name__ == '__main__':
    main()
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
diff_i = [A[i] + i + 1 for i in range(N)]
diff_j = [i + 1 - A[i] for i in range(N)]
diff = set(diff_i) & set(diff_j)
ans = 0
for d in diff:
    ans += diff_i.count(d) * diff_j.count(d)
print(ans)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

cnt1 = {}
cnt2 = {}

for i in range(N):
    tmp1 = A[i] + i + 1
    tmp2 = i + 1 - A[i]
    if tmp1 not in cnt1:
        cnt1[tmp1] = 1
    else:
        cnt1[tmp1] += 1
    if tmp2 not in cnt2:
        cnt2[tmp2] = 1
    else:
        cnt2[tmp2] += 1

diff = set(list(cnt1.keys())) & set(list(cnt2.keys()))

ans = 0
for d in diff:
    ans += cnt1[d] * cnt2[d]
print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
A1 = [[-a-i,i] for i, a in enumerate(A)]
A2 = [[a-i,i] for i, a in enumerate(A)]
A1.sort()
A2.sort()
i = j = 0
cnt = 0
while i < N and j < N:
    if A1[i][0] == A2[j][0]:
        buf1 = 1
        for k in range(i+1, N):
            if A1[k][0] != A1[i][0]:
                break
            buf1 += 1
        buf2 = 1
        for k in range(j+1, N):
            if A2[k][0] != A2[j][0]:
                break
            buf2 += 1
        for i_ in range(i, i+buf1):
            for j_ in range(j, j+buf2):
                if A1[i_][1] < A2[j_][1]:
                    cnt += 1
        i += buf1
        j += buf2
    elif A1[i][0] < A2[j][0]:
        i += 1
    else:
        j += 1
print(cnt)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))
A1 = [[-a-i,i] for i, a in enumerate(A)]
A2 = [[a-i,i] for i, a in enumerate(A)]
A1.sort()
A2.sort()
i = j = 0
cnt = 0
while i < N and j < N:
    if A1[i][0] == A2[j][0]:
        buf1 = 1
        for k in range(i+1, N):
            if A1[k][0] != A1[i][0]:
                break
            buf1 += 1
        buf2 = 1
        for k in range(j+1, N):
            if A2[k][0] != A2[j][0]:
                break
            buf2 += 1
        cnt += buf1 * buf2
        i += buf1
        j += buf2
    elif A1[i][0] < A2[j][0]:
        i += 1
    else:
        j += 1
print(cnt)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))
A1 = [[-a-i,i] for i, a in enumerate(A)]
A2 = [[a-i,i] for i, a in enumerate(A)]
A1.sort()
A2.sort()
i = j = 0
cnt = 0
while i < N and j < N:
    if A1[i][0] == A2[j][0]:
        buf1 = 1
        for k in range(i+1, N):
            if A1[k][0] != A1[i][0]:
                break
            buf1 += 1
        buf2 = 1
        for k in range(j+1, N):
            if A2[k][0] != A2[j][0]:
                break
            buf2 += 1
        cnt += buf1 * buf2
        i += buf1
        j += buf2
    elif A1[i][0] < A2[j][0]:
        i += 1
    else:
        j += 1
print(cnt)


# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

A1, A2 = {}, {}
for i, a in enumerate(A):
    key1 = str(-a-i)
    if key1 in A1:
        A1[key1] = (key1 in A1) * A1[key1] + 1
    else:
        A1[key1] = 1
    key2 = str(a-i)
    if key2 in A2:
        A2[key2] += 1
    else:
        A2[key2] = 1

cnt = 0
for key, value in list(A1.items()):
    if key in A2:
        cnt += value * A2[key]

print(cnt)
# Original solution
n = int(eval(input()))
a = list(map(int, input().split()))

a_p = [0]*n
a_m = [0]*n
ans = 0

for i in range(n):
    a_p[i] = a[i] + i+1
    a_m[i] = i+1 -a[i]

ans = 0
for i in range(n):
    for j in range(i+1,n):
        if a_p[i] == a_m[j]:
            ans = ans + 1

print(ans)

# Optimized solution
n = int(eval(input()))
a = list(map(int, input().split()))

ans = 0
dp = dict()

for i in range(n):
    a_p = a[i] + i+1
    a_m = i+1 -a[i]
    if a_p in dp:
        dp[a_p] = dp[a_p] + 1
    else:
        dp[a_p] = 1
    if a_m in dp:
        ans = ans + dp[a_m]


print(ans)
# Original solution
n = int(eval(input()))
a_l = list(map(int,input().split()))

count = 0
for i in range(n-1):
    for j in range(i+a_l[i]+1,n):
        if (j-i) == (a_l[j] + a_l[i]):
            count += 1

print(count)



# Optimized solution
n = int(eval(input()))
a_l = list(map(int,input().split()))
ia = list(enumerate(a_l))

x_dict = {}
y_dict = {}
for i, a in ia:
    x = i+a
    y = i-a
    if x in x_dict:
        x_dict[x] += 1
    else:
        x_dict[x] = 1
    if y in y_dict:
        y_dict[y] += 1
    else:
        y_dict[y] = 1

count = 0
for xkey in list(x_dict.keys()):
    if xkey in y_dict:
        count += x_dict[xkey] * y_dict[xkey]

print(count)
# Original solution
#coding: utf-8

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

count = 0
for i, a in enumerate(A):
    for offset in range(N - i):
        if (a + A[i + offset]) == offset:
            count += 1
print(count)


# Optimized solution
#coding: utf-8

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

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

count = 0
for j, a in enumerate(A):
    k = j - a
    if k in L:
        count += L[k]
print(count)
# Original solution
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10**7)
#import math
from itertools import combinations
def run():
    N = int(eval(input()))
    A = list(map(int, sysread().split()))

    A = [(idx, val) for idx, val in enumerate(A, 1) if val < N]
    ret = 0
    for (i,Ai), (j,Aj) in combinations(A, 2):
        if abs(i-j) == Ai+Aj:
            ret += 1

    print(ret)

if __name__ == "__main__":
    run()

# Optimized solution
# coding: utf-8
import sys
sysread = sys.stdin.readline

def run():
    N = int(eval(input()))
    A = list(map(int, sysread().split()))


    A = [(idx, val) for idx, val in enumerate(A, 1) if val < N]

    ret = 0
    store = [0] * N
    for idx, val in A:
        if idx - val > 0:
            ret += store[idx - val]
        try:
            store[idx + val] += 1
        except:
            continue
    print(ret)

if __name__ == "__main__":
    run()
# Original solution
n=int(eval(input()))
a=list(map(int,input().split()))
k=[]
ans=0
for i in range(400005):
  k.append(0)
for i in range(n):
  if i-a[i]>=0:
    ans+=k[i-a[i]]
  if a[i]+i<400005:
    k[a[i]+i]+=1
print(ans)

# Optimized solution
n=int(eval(input()))
a=list(map(int,input().split()))
thing={}
ans=0
for i in range(n):
  if i-a[i] in thing:
    ans+=thing[i-a[i]]
  if i+a[i] in thing:
    thing[i+a[i]]+=1
  else:
    thing[i+a[i]]=1
print(ans)
# Original solution
N=int(eval(input()))
A=list(map(int,input().split()))
np,nm=[],[]
for i in range(N):
    np.append(A[i]+i)
    nm.append(i-A[i])
sp,sm=sorted(np),sorted(nm)
ans=0
for i in range(N):
    p,m=np[i],nm[i]
    l,r=0,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<=p:
            l=x
        else:
            r=x
    while sm[l]==p and l>=0:
        ans+=1
        l-=1
    l,r=0,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<=m:
            l=x
        else:
            r=x
    while sp[l]==m and l>=0:
        ans+=1
        l-=1
print((ans//2))

# Optimized solution
N=int(eval(input()))
A=list(map(int,input().split()))
np,nm=[],[]
for i in range(N):
    np.append(A[i]+i)
    nm.append(i-A[i])
sp,sm=sorted(np),sorted(nm)
ans=0
for i in range(N):
    p,m=np[i],nm[i]
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<=p:
            l=x
        else:
            r=x
    tmp=l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sm[x]<p:
            l=x
        else:
            r=x
    ans+=tmp-l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<=m:
            l=x
        else:
            r=x
    tmp=l
    l,r=-1,N
    while not l+1==r:
        x=(l+r)//2
        if sp[x]<m:
            l=x
        else:
            r=x
    ans+=tmp-l
print((ans//2))
# Original solution
from collections import defaultdict

N, *A = list(map(int, open(0).read().split()))

ctr1 = defaultdict(int)
ctr2 = defaultdict(int)
for i in range(N):
    ctr2[i + A[i]] += 1
    if i - A[i] > 0:
        ctr1[i - A[i]] += 1

ans = 0
for v in ctr1:
    ans += ctr1[v] * ctr2[v]
print(ans)


# Optimized solution

from collections import defaultdict
from bisect import bisect_left

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

ctr = defaultdict(list)
for i in range(N):
    ctr[i + A[i]].append(i)

ans = 0
for i in range(N):
    v = i - A[i]
    if v in ctr:
        ans += bisect_left(ctr[v], i)

print(ans)
# Original solution
N = int(eval(input()))
A = [int(i) for i in input().split()]
dp = [0] * 10 ** 7
ans = 0
for i in range(N):
    x = i + 1 - A[i]
    if x >= 0:
        ans += dp[x]
    y = i + 1 + A[i]
    if y < 10 ** 7:
        dp[y] += 1

print(ans)


# Optimized solution
N = int(eval(input()))
A = [int(i) for i in input().split()]
INF = 2 * 10 ** 5
dp = [0] * INF
ans = 0
for i in range(N):
    i_i_ = i + 1 - A[i]
    if 0 < i_i_ < INF:
        ans += dp[i_i_]
    i_ = i + 1 + A[i]
    if 0 < i_ < INF:
        dp[i_] += 1

print(ans)
# Original solution
from collections import defaultdict
N = int(eval(input()))
A = list(map(int, input().split()))
B = A[:]
for n in range(N):
    B[n] -= (n + 1)

D = defaultdict(int)
ans = 0
for i, a, b in zip(reversed(list(range(N))), A[::-1], B[::-1]):
    ans += D[-(i + a + 1)]
    D[b] += 1

print(ans)


# Optimized solution
from collections import Counter
N = int(eval(input()))
A = list(map(int, input().split()))

P = [i + a for i, a in enumerate(A, start=1)]
Q = [j - a for j, a in enumerate(A, start=1)]

ans = 0
QC = Counter(Q)
for p in P:
    ans += QC[p]

print(ans)
# Original solution
import sys
import os
from itertools import combinations

def file_input():
    f = open('../Beginner_Contest_166/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    N=int(eval(input()))  #人数
    A=list(map(int, input().split()))   #身長

    ans=0
    # A_set=set(A)
    sum=set()
    for c in list(combinations(A,2)):
        sum.add(c[0]+c[1])
        # print(c)
        # print(str(c[0]-1)+str(c[1]-1)+" : "+str(A[c[0]-1])+str(A[c[1]-1]))
        # print(str(abs(A[c[0]-1]-A[c[1]-1]))+" : "+str(abs(c[0]-1-(c[1]-1))))
        # if abs(A[c[0]-1]+A[c[1]-1])==abs(c[0]-1-(c[1]-1)):
        #     ans+=1
    # print(sum)
    for s in sum:
        # print("sum : "+str(s))
        for i in range(N-s):
            if A[i]+A[i+s]==s:
                # print("h : "+str(i)+","+str(i+s))
                ans+=1

    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
import sys
import os
from itertools import combinations

def file_input():
    f = open('../Beginner_Contest_166/input.txt', 'r')
    sys.stdin = f

def main():
    #file_input()
    N=int(eval(input()))  #人数
    A=list(map(int, input().split()))   #身長

    ans=0
    A_set=set(A)
    sum=set()
    tmp=[x*2 for x in set(A) if A.count(x) > 1]
    sum=sum|set(tmp)
    # print(type(tmp))
    for c in list(combinations(A_set,2)):
        sum.add(c[0]+c[1])
        # print(c)
        # print(str(c[0]-1)+str(c[1]-1)+" : "+str(A[c[0]-1])+str(A[c[1]-1]))
        # print(str(abs(A[c[0]-1]-A[c[1]-1]))+" : "+str(abs(c[0]-1-(c[1]-1))))
        # if abs(A[c[0]-1]+A[c[1]-1])==abs(c[0]-1-(c[1]-1)):
        #     ans+=1
    # print(sum)
    for s in sum:
        # print("sum : "+str(s))
        for i in range(N-s):
            if A[i]+A[i+s]==s:
                # print("h : "+str(i)+","+str(i+s))
                ans+=1

    print(ans)


if __name__ == '__main__':
    main()
# Original solution
from collections import defaultdict

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

di = defaultdict(int)
dj = defaultdict(int)
for i in range(1, N+1):
  di[i + A[i-1]] += 1
  dj[i - A[i-1]] += 1

ans = 0
for key in list(di.keys()):
  ans += dj[key] * di[key]

print(ans)

# Optimized solution
from collections import defaultdict

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

ans = 0
di = defaultdict(int)
for i, a in enumerate(A):
    ans += di[i+1 - a]
    di[i+1 + a] += 1

print(ans)
# Original solution
N = int(eval(input()))
A = list(map(int, input().split()))

cnt = 0
for org in range(N-1):
    for i in range(org+A[org],N):
        if A[org]+A[i]==i-org:
            cnt+=1
print(cnt)

# Optimized solution
N = int(eval(input()))
A = list(map(int, input().split()))

L = {}
R_val = []
for i in range(N):
    if i+A[i] not in L:
        L[i+A[i]] = 0
    L[i+A[i]]+=1
    R_val.append(i-A[i])
    
ans = 0
for one in R_val:
    if one in L:
        ans+=L[one]
print(ans)
# Original solution
n = int(eval(input()))
a = list(map(int,input().split()))
save = [0]*n
#Ai + i
save = [a[i]+i for i in range(n)]
    
#j-Aj
ans = 0
for j in range(n):
    b = j-a[j]
    if(b<0):
        continue
    ans += save[0:j].count(b)

print(ans)

# Optimized solution
n = int(eval(input()))
mp = list(map(int,input().split()))

#Ai + i 
#j-Aj
ans = 0
cnt = [0]*(n+1)
for i in range(n-1):
    j=i+1
    a = mp[i]+i
    if(a<=n):
        cnt[a] += 1 
    b = j-mp[j]
    if(b<0):
        continue
    ans += cnt[b]
    

print(ans)
# Original solution
from collections import Counter
N = int(eval(input()))
A = list(enumerate(list(map(int, input().split()))))
b = Counter([x[0]+x[1]+1 for x in A])
c = Counter([x[0]-x[1]+1 for x in A])
count = 0
for x in list(b.items()):
    for y in list(c.items()):
        if x[0] == y[0]:
            count += x[1] * y[1]
print(count)

# Optimized solution
from collections import Counter
N = int(eval(input()))
A = list(enumerate(list(map(int, input().split()))))
b = Counter([x[0]+x[1]+1 for x in A])
c = Counter([x[0]-x[1]+1 for x in A])
count = 0
for x in list(b.items()):
    count += x[1] * c[x[0]]
print(count)
# Original solution
from collections import Counter

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

q1=[]
q2=[]

for i in range(n):
  q1.append(i+a[i])
  q2.append(i-a[i])

c1=Counter(q1)
c2=Counter(q2)

ans=0
for i in list(c1.keys()):
  num1=c1[i]
  num2=c2[i]
  ans+=num1*num2

print(ans)

# Optimized solution
from collections import Counter

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

q1=[]
q2=[]

for i in range(n):
  q1.append(i+a[i])
  q2.append(i-a[i])

c2=Counter(q2)

ans=0
for i in q1:
  ans+=c2[i]

print(ans)
# Original solution
N = int(eval(input()))

A = list(map(int, input().split()))
check = []
ans = 0


for i, v in enumerate(A):
    if v in check:
        ans += check.count(v)
    check.append(-v)
    check = list([x+1 for x in check])

print(ans)
    

# Optimized solution
N = int(eval(input()))

A = list(map(int, input().split()))
check = {}
ans = 0


for i, v in enumerate(A):
    if (i-v) in check:
        ans += check[i-v]
    if v+i in check:
        check[v+i] += 1
    else:
        check[v+i] = 1

print(ans)
# Original solution
from collections import Counter

N,*A = list(map(int,open(0).read().split()))
#j - i = Aj + Ai
#j - Aj = Ai + i
#L = i + Ai, R = j - Aj とおく
L = []
R = []
for i in range(N):
    L.append(i+1 + A[i])
    R.append(i+1 - A[i])
l = Counter(L)
r = Counter(R)
 
#print(l)
#print(r)

cnt = 0
a=[]
for i in range(1,N+1):
    if i in l and i in r:
        cnt += l[i]*r[i]
        a.append(i)
print(cnt)

# Optimized solution
from collections import Counter

N,*A = list(map(int,open(0).read().split()))
#j - i = Aj + Ai
#j - Aj = Ai + i
#L = i + Ai, R = j - Aj とおく
L = []
R = []
for i in range(N):
    L.append(i+1 + A[i])
    R.append(i+1 - A[i])
l = Counter(L)
r = Counter(R)
 
cnt = 0
a = []
for i in range(1,N+1):
    if i in l and i in r:
        cnt += l[i] * r[i]
        a.append(i)
print(cnt)