Problem:


Score: 500 points

Problem Statement

You are the top spy of AtCoder Kingdom. To prevent the stolen secret from being handed to AlDebaran Kingdom, you have sneaked into the party where the transaction happens.

There are N attendees in the party, and they are given attendee numbers from 1 through N. The height of Attendee i is A_i.

According to an examination beforehand, you know that a pair of attendees satisfying the condition below will make the transaction.

The absolute difference of their attendee numbers is equal to the sum of their heights.

There are \frac{N(N-1)}{2} ways to choose two from the N attendees and make a pair. Among them, how many satisfy the condition above?

P.S.: We cannot let you know the secret.

Constraints

All values in input are integers.

2 \leq N \leq 2 \times 10^5

1 \leq A_i \leq 10^9\ (1 \leq i \leq N)

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \dots A_N

Output

Print the number of pairs satisfying the condition.

Sample Input 1

6
2 3 3 1 3 1

Sample Output 1

3

A_1 + A_4 = 3, so the pair of Attendee 1 and 4 satisfy the condition.

A_2 + A_6 = 4, so the pair of Attendee 2 and 6 satisfy the condition.

A_4 + A_6 = 2, so the pair of Attendee 4 and 6 satisfy the condition.

No other pair satisfies the condition, so you should print 3.

Sample Input 2

6
5 2 4 2 8 8

Sample Output 2

0

No pair satisfies the condition, so you should print 0.

Sample Input 3

32
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5

Sample Output 3

22



Sample input:
6
2 3 3 1 3 1


Sample output:
3

Submission status: Accepted

Solution code:
#coding: utf-8

N = int(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)

Submission status: Accepted

Solution code:
import collections

n = int(input())

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


l = [a[i] +i+1 for i in range(n)]
r = [i+1 -a[i] for i in range(n)]

L = collections.Counter(l)
R = collections.Counter(r)

c = 0

for i in L.keys():
    c += L.get(i, 0) * R.get(i, 0)

print(c)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from itertools import product
from collections import Counter
# from itertools import combinations


def solve(N, A):
    B = [i - A[i] for i in range(N)]
    C = [i + A[i] for i in range(N)]
    Bc = Counter(B)
    Cc = Counter(C)
    ct = 0
    for k, i in Bc.items():
        if k in Cc:
            ct += i * Cc[k]
    print(ct)
    # bg = []
    # sm = []
    # # cl = set()
    # for i in range(N):
    #     if A[i] <= i - 1:
    #         bg.append(i)
    #         # cl.add(i)
    #     if A[i] >= 1 - i:
    #         sm.append(i)
    #         # cl.add(i)
    # # L = list(combinations(cl, 2))
    # L = list(product(bg, sm))
    # ct = 0
    # for l in L:
    #     if l[0] > l[1]:
    #         if abs(l[0] - l[1]) == A[l[0]] + A[l[1]]:
    #             ct += 1
    # print(ct)
    # # L = list(combinations(range(N), 2))
    # # ct = 0
    # # for l in L:
    # #     if abs(l[0] - l[1]) == A[l[0]] + A[l[1]]:
    # #         ct += 1
    # # print(ct)
    # return

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
            for line in sys.stdin:
                for word in line.split():
                    yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    A = [int(next(tokens)) for _ in range(N)]
    solve(N, A)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
from collections import defaultdict
a = list(map(int,input().split()))
ans = 0
dp = defaultdict(int)
for e,i in enumerate(a,1):
    if  e - i>= 0 :ans += dp[e-i]
    dp[i+e]+=1
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
S,D=[0]*N,[0]*N

for i in range(N):
    if A[i]+i<N:S[A[i]+i] +=1
    if i-A[i]>0:D[i-A[i]] += 1

ans=0
for l in range(N):
    ans += S[l]*D[l]

print(ans)

Submission status: Accepted

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

from copy import deepcopy

B = deepcopy(A)

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

from collections import Counter

C = Counter(A)
D = Counter(B)

E = list(C.keys())

ans = 0
for i in E:
    ans += C[i]*D[i]

print(ans)

Submission status: Accepted

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

lr = [[0,0] for i in range(n)]

for i in range(n):
  l = i+a[i]
  if l < n:
    lr[l][0] += 1
  r = i-a[i]
  if r > 0:
    lr[r][1] += 1
count = 0
for i in range(n):
  count += lr[i][0] * lr[i][1]
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
a=list(map(int,input().split()))
d1=defaultdict(int)
d2=defaultdict(int)

ans=0
for g in range(n):
    ans+=d1[a[g]-g]
    ans+=d2[a[g]+g]
    d1[-a[g]-g]+=1
    d2[-a[g]+g]+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

L = [i + a for i, a in enumerate(A)]
R = [i - a for i, a in enumerate(A)]

cL = Counter(L)
cR = Counter(R)

ans = 0
for i in cL.keys():
  ans += cL[i] * cR[i]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N=int(input())
alist=list(map(int,input().split()))

bdic=defaultdict(int)
cdic=defaultdict(int)
for i in range(N):
  bdic[alist[i]+i]+=1
  cdic[-alist[i]+i]+=1
#print(bdic)
#print(cdic)

answer=0
for b,bv in bdic.items():
  answer+=bv*cdic[b]
  
print(answer)

Submission status: Accepted

Solution code:
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))
def ism():return map(str,input().split())
def isl():return list(map(str,input().split()))

n = ii()
A = iil()

#ここから解説見る
ans = 0
d = {}
for i,item in enumerate(A):
    ans += d.get(i-item,0)
    d[i+item] = d.get(i+item,0)+1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


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

L = defaultdict(int)
R = defaultdict(int)
for i, v in enumerate(A):
    L[i + v] += 1
    R[i - v] += 1
print(sum(L.get(i, 0) * R.get(i, 0) for i in range(n)))

Submission status: Accepted

Solution code:
#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

cnt = 0
d = defaultdict(int)
for i, a in enu(A):
    l = (i+1) + a
    r = (i+1) - a
    cnt += d[r]
    d[l] += 1
print(cnt)

Submission status: Accepted

Solution code:
n = int(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 x_dict.keys():
    if xkey in y_dict:
        count += x_dict[xkey] * y_dict[xkey]

print(count)

Submission status: Accepted

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

count = 0

def solve():
    from collections import Counter
    cc=Counter()
    ans=0
    for i,val in enumerate(A,1):
        if i-val>0:
            ans+=cc[i-val]
        cc[i+val]+=1
    print(ans)
    
def dfs(x, y):
    global count
    if x >= N or y >= N:
        return
    
    if (A[x]+A[y]) == y-x:
        count += 1

    if x+1 >= N and y+1 >= N:
        return
        
    if y+1 >= N:
        dfs(x+1, x+2)
    else:
        dfs(x, y+1)


#dfs(0, 1)
#print(count)
solve()

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
cnt = 0
# dp = [0]*N
# for i in range(N-1):
#     t = A[i]
#     if t > 200000:
#         continue
#     for j in range(i+t+1, N):
#         if j-i == t+A[j]:
#             cnt += 1
# print(cnt)

# i<j
# j-i = A[i]+A[j]
# j-A[j] = i+A[i]
# j+A[j] = i-A[i]
MAX = 2*10**5

dpL = [0]*(MAX)
dpR = [0]*(MAX)
for i in range(N):
    num = A[i]
    if num > 200000:
        continue   
    if i+num < MAX:
        dpL[i+num] += 1
    if i >= num:
        dpR[i-num] += 1

for i in range(MAX):
    l = dpL[i]
    r = dpR[i]
    cnt += l*r

print(cnt)

Submission status: Accepted

Solution code:
import collections

N = int(input())
As =  list(map(int, input().split()))
Bs = [As[i]+i+1 for i in range(N)]
Cs =  collections.Counter(Bs)

rlt = 0
#print(Cs)
for j in range(1,N):
  c = As[j] - (j+1)
  rlt += Cs[-c]
  #print(c)

print(rlt)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
C=[0]*N

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

B.sort()
B.insert(0,-2000000000)
B.append(2000000000)
C.sort()
ans=0
for a in C:
    l1=0
    r1=N
    while r1-l1>1:
        m1=(l1+r1)//2
        if B[m1] < a:
            l1=m1
        else:
            r1=m1
    l2=0
    r2=N
    while r2-l2>1:
        m2=(l2+r2)//2
        if B[m2] <= a:
            l2=m2
        else:
            r2=m2
    ans += l2-l1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sysread = sys.stdin.readline

def run():
    N = int(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()

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
ans=0
cnt = defaultdict(int)
for i in range(N):
  x = i - A[i]
  y = i + A[i]
  cnt[y] += 1
  ans += cnt[x]
        
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
S = [0]*N
D = [0]*N

for i in range(N):
    if A[i]+i < N:
        S[A[i]+i] += 1
    if i - A[i] > 0:
        D[i - A[i]] += 1
ans = 0
for l in range(N):
    ans += S[l]*D[l]
    

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict


def input():
    return sys.stdin.readline().strip()


def main():
    N = int(input())
    A = list(map(int, input().split()))
    L = defaultdict(list)
    R = defaultdict(list)
    for i in range(N):
        L[A[i] + i].append(i)
        R[i - A[i]].append(i)
    K = list(L.keys())

    answer = 0
    for k in K:
        l = len(L[k])
        r = len(R[k])
        answer += l * r
    print(answer)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:


from collections import Counter
n = int(input())
a = list(map(int, input().split()))
aplusi = [item+i for i,item in enumerate(a)]
iminusa = [i-item for i,item in enumerate(a)]
c1 = Counter(aplusi)
c2 = Counter(iminusa)
out = 0
for k,v in c1.items():
    if k in c2:
        out += v * c2[k]
print(out)

Submission status: Accepted

Solution code:
n = int(input())

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

a = [0] + a

from collections import defaultdict

c = defaultdict(int)

ret = 0
for i in range(1, n + 1):
    c[i + a[i]] += 1

    max_diff = i - a[i]
    ret += c[max_diff]

print(ret)

Submission status: Accepted

Solution code:

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

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

ip=[0]*n
jm=dict()
for i in range(n):
    ip[i]=i+a[i]
    if i-a[i] in jm:
        jm[i-a[i]]+=1
    else:
        jm[i-a[i]]=1

icnt=0
for i in range(n):
    if ip[i] in jm:
        icnt+=jm[ip[i]]
            
print(icnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
d_i = defaultdict(list)
d_j = defaultdict(list)

N = int(input())
A = [int(a) for a in input().split()]

for i in range(N):
    d_i[i-A[i]].append(i)
    d_j[i+A[i]].append(i)

cnt = 0
for key in d_j.keys():
    arr_i = d_i[key]
    arr_j = d_j[key]
    cnt += len(arr_j) * len(arr_i)
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict


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

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

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#create date: 2020-05-03 21:37

import sys
stdin = sys.stdin
from collections import defaultdict

import numpy as np

def ns(): return stdin.readline().rstrip()
def ni(): return int(ns())
def na(): return list(map(int, stdin.readline().split()))

def main():
    n = ni()
    a = np.array(na())
    b = np.arange(1, n+1)
    c = a + b
    d = b - a
    l = defaultdict(lambda: 0)
    ans = 0
    for ci in c:
        l[ci] += 1
    for di in d:
        ans += l[di]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Ai = dict()
ans = 0
for i, v in enumerate(A):
    ai = i + v
    if ai in Ai:
        Ai[ai].append(i)
    else:
        Ai[ai] = [i]
for i, v in enumerate(A):
    aj = i - v
    if aj in Ai:
        ans += len(Ai[aj])
print(ans)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))


ans = 0
t = collections.defaultdict(int)
t2 = collections.defaultdict(int)
for i, x in enumerate(A):
    t[i-x] += 1
    t2[x+i] += 1
for i, x in enumerate(A):
    ans += t[x+i]
    ans += t2[i-x]

print(ans // 2)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

kouho = defaultdict(int)
ans = 0
for i in range(n):
    kouho[A[i] + (i + 1)] += 1
    ans += kouho[(i + 1) - A[i]]

print(ans)

Submission status: Accepted

Solution code:
def main():
    from collections import Counter
    n = int(input())
    As = list(map(int,input().split(" ")))
    
    cnts = Counter()
    dp = [0]*n
    cnts[As[0]+1]+=1
    for i in range(1,n):
        dp[i] =dp[i-1] + cnts.get(i+1-As[i],0)
        cnts[As[i]+i+1]+=1
    print(dp[n-1])
main()

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
alist = list(map(int, input().split()))
alist = [0] + alist
sumlist = []
# (j, wj)のリストを作る
for i in range(1,N+1):
    sumlist.append(i+alist[i])
sumlist.sort()
sum_cnt = Counter(sumlist)
ans = 0
# 差と一致するものを探す
for i in range(1, N+1):
    diff = i - alist[i]
    if diff in sum_cnt:
        ans += sum_cnt[diff]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
C=[0]*N

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

B.sort()
B.insert(0,-2000000000)
B.append(2000000000)
C.sort()
ans=0
for a in C:
    l1=0
    r1=N
    while r1-l1>1:
        m1=(l1+r1)//2
        if B[m1] < a:
            l1=m1
        else:
            r1=m1
    l2=0
    r2=N
    while r2-l2>1:
        m2=(l2+r2)//2
        if B[m2] <= a:
            l2=m2
        else:
            r2=m2
    if l2==0 and l1 == -1:
        pass
    else:
        ans += l2-l1

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
su = dict()
sd = dict()
for i in range(n):
    if a[i] + i + 1 in su:
        su[a[i] + i + 1] += 1
    else:
        su[a[i] + i + 1] = 1
    if a[i] - i - 1 in sd:
        sd[a[i] - i - 1] += 1
    else:
        sd[a[i] - i - 1] = 1
fsu = []
for d in su:
    fsu.append([d, su[d]])
fsu.sort()
fsd = []
for d in sd:
    fsd.append([d, sd[d]])
fsd.sort()
s = 0
i1 = len(fsu) - 1
j1 = 0
#print(fsu)
#print(fsd)
while (i1 >= 0 and j1 <= len(fsd)-1):
    if (fsu[i1][0] + fsd[j1][0] == 0):
                s+=fsu[i1][1] * fsd[j1][1]
                i1-=1
    elif (fsu[i1][0] + fsd[j1][0] > 0):
                i1-=1
    elif (fsu[i1][0] + fsd[j1][0] < 0):
                j1+=1

print(s)

Submission status: Accepted

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

tmp1 = []
tmp2 = []
from collections import defaultdict
d1 = defaultdict(int)
d2 = defaultdict(int)
for i in range(N):
    tmp1 = A[i] + i
    tmp2 = i - A[i]
    d1[tmp1] += 1
    d2[tmp2] += 1

ans = 0

for key1, value1 in d1.items():
    if d2[key1]:
        ans += value1 * d2[key1]
print(ans)

Submission status: Accepted

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

ans = 0
b = {}
for i in range(n):
    l = a[i] + (i+1)
    r = (i+1) - a[i]
    if r in b:
        ans += b[r]
    if l in b:
        b[l] += 1
    else:
        b[l] = 1

print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter
    N=int(sys.stdin.readline())
    A=list(map(int,sys.stdin.readline().split()))
    C=Counter([i+x for i,x in enumerate(A)])
    output=0
    for key,val in Counter([i-x for i,x in enumerate(A)]).items():
        if key in C.keys():
            output+=val*C[key]
    print(output)

main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
c=[0]*n
d=0
sums=0
for j in range(n):
    if j-a[j]<1:
        das=0
    else:
        b[j-a[j]]=b[j-a[j]]+1
    if j+a[j]>n-2:
        das=0
    else:
        c[j+a[j]]=c[j+a[j]]+1
for k in range(n):
    d=b[k]*c[k]
    sums=sums+d
print(sums)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import numpy as np

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


x = np.array(a[1:])-a[0]+np.arange(1, n)
# print(x)

y = np.array(a[1:])+a[0]-np.arange(0, n-1)
# print(y)

count = {}
ans = 0
for i in range(0, n-1):
    if not x[i] in count:
        count[x[i]] = 1
    else:
        count[x[i]] += 1

    if y[i] == 1:
        ans += 1
    if -y[i]+1 in count:
        ans += count[-y[i]+1]
# print(count)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
d = [0]*(10**6)
ans = 0
for i in range(N):
    m = i+1+A[i]
    if m < 10**6:
        d[i+1+A[i]] += 1
    
for i in range(1,N+1):
    f = A[-i]+N+1-i-(2*A[-i])
    if f >= 0 and f < 10**6:
        ans += d[f]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

x = Counter([i + 1 + X[i] for i in range(N)])
y = Counter([i + 1 - X[i] for i in range(N)])

ans = 0
for k, v in x.items():
    ans += v * y[k]
    
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(300000)
from collections import defaultdict

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N = I()
A = LMI()

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

ans = 0
for i, a in enumerate(A):
    c = d[a + i + 1]
    if c > 0:
        ans += c
print(ans)

Submission status: Accepted

Solution code:
import collections
def main():
    N = int(input())
    A = list(map(int, input().split()))

    B = [a+i for i, a in enumerate(A)]
    C = [a-i for i, a in enumerate(A)]

    
    c = collections.Counter(C)

    ans = 0
    for b in B:
        ans += c.get(-b, 0)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


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

    ans = 0
    b = {}
    for i in range(N):
        l = A[i] + (i+1)
        r = (i+1) - A[i]
        if r in b:
            ans += b[r]
        if l in b:
            b[l] += 1
        else:
            b[l] = 1

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H):
    '''
    H is number of rows
    A列、B列が与えられるようなとき
    ex1)A,B=read_col(H)    ex2) A,=read_col(H) #一列の場合
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return tuple(map(list, zip(*ret)))


def read_matrix(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(list(map(int, read().split())))
    return ret
    # return [list(map(int, read().split())) for _ in range(H)] # 内包表記はpypyでは遅いため


MOD = 10**9 + 7
INF = 2**31  # 2147483648 > 10**9
# default import
from collections import defaultdict, Counter, deque
from operator import itemgetter
from itertools import product, permutations, combinations
from bisect import bisect_left, bisect_right  # , insort_left, insort_right
from math import gcd


# i<jに対して
# Ai-i = -Aj-j か Ai+i=-Aj+jがなり立つ組を探せばよい
N = read_a_int()
A = read_ints()


def ret_kumiawase(X, Y):  # どっちもリスト
    ret = 0
    cnt = Counter()
    for i in range(N - 1, -1, -1):
        ret += cnt[X[i]]  # X[i]の数字の個数を加算する
        cnt.update([Y[i]])  # X[i]の数字の個数を加算する
    return ret


# 前者から
Ai = []
for i, a in enu(A):
    Ai.append(a - i)
Aj = []
for i, a in enu(A):
    Aj.append(-a - i)
ans = ret_kumiawase(Ai, Aj)


# 後者
Ai = []
for i, a in enu(A):
    Ai.append(a + i)
Aj = []
for i, a in enu(A):
    Aj.append(-a + i)
ans += ret_kumiawase(Ai, Aj)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
di1 = {}
di2 = {}
for i, j in enumerate(a):
    if i-j in di1:
        di1[i-j] += 1
    else:
        di1[i-j] = 1
    if i+j in di2:
        di2[i+j] += 1
    else:
        di2[i+j] = 1

ans = 0
for i, j in di1.items():
    if i not in di2:
        continue
    ans += di2[i]*j
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding: utf-8 -*-

# import numpy as np
# from itertools import *
# from collections import *
from collections import Counter

# S = input().split()
# N = int(input().split())
# N, K = [int(x) for x in input().split()]

N = int(input())
A = [int(x) for x in input().split()]

number = range(1, N+1)
numhei = [0] * N
for n in range(N):
    numhei[n] = number[n] + A[n]

c = Counter(numhei)
count = 0
for n in number:
    count += c[n - A[n-1]]

print(count)

Submission status: Accepted

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

fromLeftA = [-1]*n

for i in range(n):
    fromLeftA[i] = a[i] - i

ans = 0
ldList = [0]*(n*2)

for i in reversed(range(n)):
    if 0 <= fromLeftA[i]+n and fromLeftA[i]+n < n*2:
        ldList[fromLeftA[i]+n] += 1
    if 0 <= -1*a[i]-i+n and -1*a[i]-i+n < n*2:
        ans += ldList[-1*a[i]-i+n]

print(ans)

Submission status: Accepted

Solution code:
n,*l=map(int,open(0).read().split())
from collections import*
d=defaultdict(int)
a=0
for i in range(n): d[i+l[i]]+=1; a+=d[i-l[i]]*(i>l[i])
print(a)

Submission status: Accepted

Solution code:
from collections import Counter
N=int(input())
A=[int(i) for i in input().split(" ")]

A2=[i-A[i] for i in range(N)]
A3=[i+A[i] for i in range(N)]

c2=Counter(A2)
c3=Counter(A3)

retval=0
for key in c2+c3:
    retval+=c2[key]*c3[key]

print(retval)

Submission status: Accepted

Solution code:
from operator import itemgetter
from collections import defaultdict
N = int(input())
A = [int(v) for v in input().split()]
cnt = 0
left_list = [i + a for i, a in enumerate(A, 1)]
right_list = [i - a for i, a in enumerate(A, 1)]
right_dict = defaultdict(set)
for i, right in enumerate(right_list, 1):
    right_dict[right].add(i)
for i, left in enumerate(left_list, 1):
    pair_num = len(right_dict[left])
    cnt += pair_num
print(cnt)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(l):
	n = len(l)
	ans = 0
	d1,d2 = defaultdict(int),defaultdict(int)
	L = []
	for i in range(n):
		L.append([l[i],i])
	ans = 0
	L = sorted(L)
	for j in range(n):
		i = L[j][1]
		zz = L[j][0]
		d1[i-zz] += 1
		d2[i+zz] += 1
	for i in d1:
		ans += d1[i]*d2[i]
	return ans

N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")

n = int(input())
a = list(myinput())

# b = []
c = []
for i in range(n):
    # b.append(i+a[i])
    if i<a[i]:
        pass
    else:
        c.append(i-a[i])
# print(b)
# print(c)

c.sort()
# print(c)

ans = 0
for i in range(n):
    m = i + a[i]
    a1 = bisect_left(c,m)
    a2 = bisect_right(c,m)
    ans += a2 - a1
print(ans)

Submission status: Accepted

Solution code:
# ANSHUL GAUTAM
# IIIT-D

from math import *
from copy import *					# ll = deepcopy(l)
from heapq import *					# heappush(hp,x)
from string import *				# alpha = ascii_lowercase
from random import *				# l.sort(key=lambda l1:l1[0]-l1[1]) => ex: sort on the basis difference
from bisect import *				# bisect_left(arr,x,start,end)  => start and end parameters are temporary
from sys import stdin				# bisect_left return leftmost position where x should be inserted to keep sorted
from sys import maxsize				# minn = -maxsize
from operator import *				# d = sorted(d.items(), key=itemgetter(1))
from itertools import *				# pre = [0] + list(accumulate(l))
from collections import Counter		# d = dict(Counter(l))
from collections import defaultdict # d = defaultdict(list)

'''

'''

def solve(l):
	n = len(l)
	ans = 0
	d1,d2 = defaultdict(int),defaultdict(int)
	L = []
	for i in range(n):
		L.append([l[i],i])
	ans = 0
	L = sorted(L)
	# print('L:',L)
	for j in range(n):
		i = L[j][1]
		zz = L[j][0]
		# print(L[j],i,zz)
		d1[i-zz] += 1
		d2[i+zz] += 1
	# print(dict(d1))
	# print(dict(d2))
	for i in d1:
		ans += d1[i]*d2[i]
	return ans

N = int(stdin.readline())
l = list(map(int, stdin.readline().rstrip().split()))
ans = solve(l)
print(ans)

Submission status: Accepted

Solution code:
n,*l=map(int,open(0).read().split())
from collections import*
c=Counter()
a=0
for i in range(n): c[i+l[i]]+=1; a+=c[i-l[i]]*(i>l[i])
print(a)

Submission status: Accepted

Solution code:
N =int(input())
A = list(map(int,input().rstrip().split(" ")))
Aq = []
DP = [0 for i in range(5 * 10 ** 5)]
DPP = []
ans = 0
for i in range(N):
    if i >= A[i]:
        ans += DP[i - A[i]]
    if A[i] <= N:
        DP[A[i] + i] += 1
    
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
import collections

count = 0

count_dict = collections.defaultdict(int)

for idx, a in enumerate(A):
    count_dict[idx-a] += 1

for idx, a in enumerate(A):
    if idx+a in count_dict:
        count += count_dict[idx+a]
        continue
    # for i in range(idx+a+1, N):
    #     if a + A[i] == i - idx:
    #         count += 1
    #         count_dict[idx+a+1] += 1
# print(count_dict)

print(count)

Submission status: Accepted

Solution code:
import numpy as np
n=int(input())
ans=0
a=list(map(int,input().split()))
now=max(a)
noww=now
k=n+2*now
matc=[0]*(n+2)
mat2=[0]*(n+2)
for i in range(n):
  neg=i-a[i]
  pos=i+a[i]
  if neg>=0:
    matc[neg]+=1
  if pos<=n:
    mat2[pos]+=1
  now+=1
#print(matc)
for j in range(n+2):
  ans+=matc[j]*mat2[j]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
Hash1=defaultdict(lambda:0)
Hash2=defaultdict(lambda:0)
Hash3=defaultdict(lambda:0)
Hash4=defaultdict(lambda:0)
N=int(input())
arr=list(map(int,input().split()))
arr.insert(0,-1)
count=0
for i in range(1,N+1):
    count+=Hash4[i-arr[i]]
    Hash1[arr[i]-i]+=1
    Hash2[-arr[i]-i]+=1
    Hash3[i-arr[i]]+=1
    Hash4[i+arr[i]]+=1
# for i in Hash1.keys():
#     count+=Hash2[i]
# for j in Hash4.keys():
#     count+=Hash3[j]
print(count)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int, input().split()))

B = [0 for _ in range(N)]
C = [0 for _ in range(N)]
for i in range(N):
  B[i] = i - A[i]
  C[i] = i + A[i]
lis1 = collections.Counter(B)
lis2 = collections.Counter(C)
count = 0
for key, value in lis1.items():
  if key in lis2:
    count += value * lis2[key]
print(count)

Submission status: Accepted

Solution code:
import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
from collections import Counter
def resolve():
    N = ir()
    A = lr()
    sA = [A[i]-i-1 for i in range(N)]
    c = Counter(sA)
    # print(c, sA)
    ans = 0
    for i in range(N):  
        c[sA[i]] -= 1
        c.setdefault(-(A[i]+i+1), 0)
        ans += c[-(A[i]+i+1)]
    print(ans)
resolve()