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:
from collections import Counter
n = int(input())
ai = list(map(int,input().split()))
pl = []
mi = []
for i in range(n):
    pl.append(i+ai[i])
    mi.append(i-ai[i])
x = Counter(pl)
y = Counter(mi)
cnt = 0
for i in x.keys():
    cnt += x[i]*y[i]
print(cnt)

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def LI(): return list(map(int, stdin.readline().split()))
def LS(): return list(stdin.readline())

import collections
n = int(input())
a = LI()
ans = 0
r = []
l = []
for i in range(n):
    r.append(i+a[i])
    l.append(i-a[i])
cr =  collections.Counter(r)
cl =  collections.Counter(l)
for k,v in cr.items():
    ans += v*cl[k]
print(ans)

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
l=[]
r=[]
for i in range(n):
  l.append(i+a[i]+1)
  r.append(i-a[i]+1)
cl=collections.Counter(l)
cr=collections.Counter(r)
ans=0
for k,v in cl.items():
  ans+=v*cr[k]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
from collections import Counter
ai,aj=[],[]
for i in range(n):
  aj.append(i-a[i])
  ai.append(i+a[i])
c1=Counter(ai)
c2=Counter(aj)
ans=0
for k in c1.keys():
  ans+=c1[k]*c2[k]
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

INF = float("inf")

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 mycount(ls,x):
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

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]
    ans += mycount(c,m)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
plus_lis = [A[i] + i for i in range(N)]
minus_lis = [k - A[k] for k in range(N)]

ans_lis = [0] * 10 ** 6
for x in plus_lis:
    if x < 10 ** 6:
        ans_lis[x-1] += 1
for y in minus_lis:
    if y > 0:
        ans += ans_lis[y-1]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
d1=defaultdict(int)
d2=defaultdict(int)
n=int(input())
a=list(map(int,input().split()))
s=0
for i in range(n):
    d1[a[i]+i+1]+=1
    d2[i+1-a[i]]+=1
for v in d1.keys():
    s+=d1[v]*d2[v]
print(s)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
alist=list(map(int,input().split()))
a1=[]
a2=[]
for i,a in enumerate(alist):
  a2.append(i-a)
  a1.append(i+a)
aa=Counter(a2)
count=0
for k in a1:
  count+=aa.get(k,0)
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
n = int(input())
A = list(map(int, input().split()))

L = dd(set)
R = dd(set)
for i, a in enumerate(A):
    x = i + a
    L[x].add(i)
    x = i - a
    R[x].add(i)

#print(L)
#print(R)

counter = 0
for num in list(set(L.keys()) & set(R.keys())):
    counter += len(L[num]) * len(R[num])

print(counter)

Submission status: Accepted

Solution code:
N = int(input())

X1_dict = {}
X2_dict = {}
inp_list = list(map(int, input().split(" ")))
for i, a_i in enumerate(inp_list):
	X1 = i + 1 + a_i
	X2 = i + 1 - a_i
	if X1 in X1_dict.keys():
		X1_dict[X1] += 1
	else:
		X1_dict[X1] = 1
	if X2 in X2_dict.keys():
		X2_dict[X2] += 1
	else:
		X2_dict[X2] = 1

answer = 0
for key, value in X1_dict.items():
	if key in X2_dict.keys():
		answer += value * X2_dict[key]
		
print(answer)

Submission status: Accepted

Solution code:
def lower_bound(arr,tar):
    def _lower_bound(first,length):
        if(length==0):
            return first

        half = length//2
        middle = first+half
        if arr[middle]<tar:
            return _lower_bound(middle+1,length-half-1)
        else:
            return _lower_bound(first,half)
    return _lower_bound(0,len(arr))

def upper_bound(arr,tar):
    def _upper_bound(first,length):
        if(length==0):
            return first

        half = length//2
        middle = first+half
        if arr[middle]>tar:
            return _upper_bound(first,half)
        else:
            return _upper_bound(middle+1,length-half-1)
    return _upper_bound(0,len(arr))

N=int(input())
a=list(map(int,input().split()))
L = [(i+1)+a[i] for i in range(N)]
R = [(i+1)-a[i] for i in range(N)]
R.sort()

s=0
for it in L:
    s+=upper_bound(R,it)-lower_bound(R,it)
print(s)

Submission status: Accepted

Solution code:
from collections import Counter

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

l = []
r = []
for i,j in enumerate(A):
    l.append(i+j)
    r.append(i-j)

num_l = Counter(l)
num_r = Counter(r)

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

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(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 di.keys():
  ans += dj[key] * di[key]

print(ans)

Submission status: Accepted

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

Aii=[0]*(N)
Ajj=[0]*(N)

for i in range(N):
    x=A[i]+i+1
    y=i+1-A[i]
    if 1<x<N: Aii[x]+=1
    if 1<y<N: Ajj[y]+=1

ans=0
for i in range(N):
    ans+=Aii[i]*Ajj[i]

print(ans)

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int, input().split()))
ans=0
b=[]
c=[]
for i in range(n):
    b.append(i+a[i])
    c.append(i-a[i])
b=collections.Counter(b)
c=collections.Counter(c)
for i in range((10**5)*2):
    ans+=b[i]*c[i]



print(ans)

Submission status: Accepted

Solution code:
# Problem E - This Message Will Self-Destruct

# input
N = int(input())
a_nums = list(map(int, input().split()))

# initialization
num_dic = {}
ans = 0

# count
for i in range(1, N+1):
    a = a_nums[i-1] + i
    if not a in num_dic:
        num_dic[a] = 1
    else:
        num_dic[a] += 1

# count 2
for j in range(1, N+1):
    b = j - a_nums[j-1]
    if b in num_dic:
        ans += num_dic[b]

# output
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=list(map(int,input().split()))
L=[]
R=[]
for i in range(n):
  L.append(i+A[i])
  R.append(i-A[i])
from collections import Counter
zisyo=Counter(R)
ans=0
for i in L:
  ans=ans+zisyo.get(i,0)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
plus = []
ans = 0
for i in range(N):
    plus.append(i+1+A[i])
plus_cnt = Counter(plus)
for j in range(N):
    ans += plus_cnt[j+1-A[j]]

print(ans)

Submission status: Accepted

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

L = []
R = []
for i, A in enumerate(A_list):
    L.append(i+A)
    R.append(i-A)


import collections
r_dict = collections.Counter(R)
ans = 0
for l in L:
    ans += r_dict.get(l, 0)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict

# 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(A, N):
    d1 = defaultdict(int)
    d2 = defaultdict(int)

    for i, a in enumerate(A):
        d1[i+a] += 1
    
    for i, a in enumerate(A):
        d2[i-a] += 1

    cnt = 0
    for x in set(list(d1.keys())+list(d2.keys())):
        cnt += d1[x]* d2[x]

    print(cnt)
    pass

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    main(A, N)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from collections import defaultdict

# 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(A, N):
    d1 = defaultdict(int)
    d2 = defaultdict(int)

    for i, a in enumerate(A):
        d1[i+a] += 1
    
    for i, a in enumerate(A):
        d2[i-a] += 1

    cnt = 0
    for x in list(d1.keys())+list(d2.keys()):
        cnt += d1[x]* d2[x]

    print(cnt//2)
    pass

if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    main(A, N)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int, input().split(' ')))
l, r = [], []
for i in range(n):
    l.append(i + a[i])
    r.append(i - a[i])
c = collections.Counter(r)
ans = 0
for i in l:
    ans += c.get(i, 0)
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int,input().split()))
ma = {}
for i,l in enumerate(li):
    if i+l+1 not in ma:
        ma[i+l+1] = 1
    else:
        ma[i+l+1] += 1
#print(ma)
ans = 0
for i,l in enumerate(li):
    j = i+1
    tmp = 0
    if j-li[i] in ma:
        tmp = ma[j-li[i]]
    if j-li[i] == li[i]+j:
        tmp -=1
    ans += tmp
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    d = {}
    res = 0
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n-1, -1, -1):
        if i+a[i] in d:
            res += d[i+a[i]]
        if i-a[i] not in d:
            d[i-a[i]] = 1
        else:
            d[i-a[i]] += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    #from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    d = defaultdict(int)
    res = 0
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n-1, -1, -1):
        res += d[i+a[i]]
        d[i-a[i]] += 1
    print(res)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

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

    DL = Counter(L)
    DR = Counter(R)

    res = 0
    for k, v in DL.items():
        if DR.get(k, 0) != 0:
            res += DR.get(k) * v
        else:
            DR[k] = v

    print(res)


if __name__ == '__main__':
    resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict

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

L = defaultdict(int)
R = defaultdict(int)
for i in range(len(A)):
    L[A[i] + i] += 1
    R[i - A[i]] += 1

# print(L, R)
# print(L.keys(), R.keys())
ans = 0
for r in R.keys():
    if r in L.keys():
        ans += L[r] * R[r]
print(ans)

Submission status: Accepted

Solution code:
# E - This Message Will Self-Distruct in 5s

from collections import Counter

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

# Ai + Aj == j - i
# Aj - j == -Ai - i

# Aj - j の各値の個数
diff = Counter(a[j] - (j+1) for j in range(n))

# 各Aiについて Aj - j == -Ai - i となるjの個数を数える
count = 0
for i in range(n):
    diff[a[i] - (i+1)] -= 1  # i自身を取り除く
    count += diff[-a[i] - (i+1)]

print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

rem = defaultdict(int)
ans = 0

for i, x in enumerate(lis):
    ans += rem[i - x]
    rem[i + x] += 1
print(ans)

Submission status: Accepted

Solution code:
import collections

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

d = dict(collections.Counter([i + A[i] for i in range(N)]))
ans = sum([d.get(j - A[j], 0) for j in range(N)]) # .get()の第２引数は、第１引数がなかった場合に返す値

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
di=defaultdict(int)
dj=defaultdict(int)
N=int(input())
A=list(map(int,input().split()))
for i,a in enumerate(A):
    di[i+a]+=1
    dj[i-a]+=1
X=set(di.keys())&set(dj.keys())
ans=0
for x in X:
    ans+=di[x]*dj[x]
print(ans)

Submission status: Accepted

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

cond1s = {}
cond2s = {}

for i in range(N):
	c1 = i + 1 - As[i]
	c2 = i + 1 + As[i]
	if c1 in cond1s:
		cond1s[c1] += 1
	else:
		cond1s[c1] = 1
	if c2 in cond2s:
		cond2s[c2] += 1
	else:
		cond2s[c2] = 1

ans = 0
for k in cond1s.keys():
	if k in cond2s:
		ans += cond1s[k] * cond2s[k]

print(ans)

Submission status: Accepted

Solution code:
# A_i + A_j = j - i
# A_i + i = j - A_j
# 必ず i != j となる(A_x + x = x - A_xが成り立つとA_x = 0となり制約と反するため)

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

iList = [0] * N
jList = [0] * N
for i in range(N):
  iList[i] = A[i] + i
  jList[i] = i - A[i]
  
from collections import defaultdict
iDic = defaultdict(int)
jDic = defaultdict(int)

for i in range(N):
  iDic[iList[i]] += 1
  jDic[jList[i]] += 1
  
ans = 0
for item in iDic.items():
  ans += jDic[item[0]] * item[1]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
ans = 0
l=[]
for i in range(n):
    l.append(i-a[i])
cnt = Counter(l)
for i in range(n):
    ans += cnt[i+a[i]]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
 
d = {}
for i in range(1, n+1):
    k = i - a[i-1]
    if k in d:
        d[k] += 1
    else:
        d[k] = 1
ans = 0
for i in range(1, n+1):
    k = a[i-1]+i
    if k in d:
       ans += d[k]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from collections import Counter

N = int(input())
H = list(map(int, input().split()))
L = []
R = []

for i, j in enumerate(H):
    L.append(i+j)
    R.append(i-j)

b = Counter(R)
ans = 0

for i in L:
    ans += b.get(i,0)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

dict1 = Counter(i+n for i, n in enumerate(A))
dict2 = Counter(i-n for i, n in enumerate(A))

ans = 0
for key, value in dict1.items():
    ans += value * dict2[key]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    n = int(input())
    l = defaultdict(int)
    r = defaultdict(int)
    for i, ai in enumerate(map(int, input().split())):
        l[i - ai] += 1
        r[i + ai] += 1
    print(sum(l[i] * r[i] for i in range(1, n - 1)))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(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 b.items():
    count += x[1] * c[x[0]]
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import sys
from collections import defaultdict

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

sv = defaultdict(list)
hv = defaultdict(list)

for i, ai in enumerate(a):
    sv[ai + i + 1].append(i + 1)
    hv[(i + 1) - ai].append(i + 1)


ps = 0
for x in sv:
    ps += len(sv[x]) * len(hv[x])

print(ps)

Submission status: Accepted

Solution code:
# E - This Message Will Self-Distruct in 5s

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

# Ai + Aj == j - i
# Aj - j == -Ai - i

# Aj - j の各値の個数
diff = {}
for j in range(n):
    x = a[j] - (j+1)
    if x not in diff:
        diff[x] = 0
    diff[x] += 1

# 各Aiについて Aj - j == -Ai - i + 1 となるjの個数を数える
count = 0
for i in range(n):
    diff[a[i] - (i+1)] -= 1  # i自身を取り除く
    x = -a[i] - (i+1)
    if x in diff:
        count += diff[x]

print(count)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from collections import defaultdict 
def main():
    N = int(readline())
    A = [int(i) for i in readline().split()]
    dd_a = defaultdict(int)
    dd_b = defaultdict(int)
    for i in range(N):
        dd_a[i-A[i]] += 1
        dd_b[A[i]+i] += 1
    ans = 0
    for i in dd_a.keys():
        ans += dd_a[i] * dd_b[i]
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

ans = 0
start_idx = [0] * N
for i, a in enumerate(A):
    if i+a < N:
        start_idx[i+a] += 1
    if i-a >= 0:
        ans += start_idx[i-a]

print(ans)

Submission status: Accepted

Solution code:
import collections
 
input()
p = list(map(int, input().split()))
map1 = collections.defaultdict(lambda:0)
map2 = collections.defaultdict(lambda:0)
 
for i, v in enumerate(p):
  map1[i+v] += 1
  map2[i-v] += 1

ans = 0
for i in map1:
  if i in map2:
    ans += map1[i] * map2[i]

print(ans)

Submission status: Accepted

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

data = {}
for i in range(1, N+1):
    a = i - A[i-1]
    if a in data:
        data[a] += 1
    else:
        data[a] = 1

ans = 0
for i in range(1, N+1):
    a = A[i-1]+i
    if a in data:
       ans += data[a]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
L_dict, R_dict = {}, {}
i = 0
for ipt in input().split():
    try:
        L_dict[i + int(ipt)] += 1
    except KeyError:
        L_dict[i + int(ipt)] = 1
    try:
        R_dict[i - int(ipt)] += 1
    except KeyError:
        R_dict[i - int(ipt)] = 1
    i += 1
cnt = 0
for Lk, Lv in L_dict.items():
    try:
        cnt += R_dict[Lk] * Lv
    except KeyError:
        pass
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
D = defaultdict(int)
ans = 0

for i, x in enumerate(A, 1):
    ans += D[i-x]
    D[x+i] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
dic = defaultdict(int)

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

for i, a in enumerate(A):
    dic[i + a] += 1

counter = 0
for i, a in enumerate(A):
    counter += dic[i-a]

print(counter)

Submission status: Accepted

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

dicplus = {}
dicmins = {}
for i in range(n):
	b = i + a[i]
	c = i - a[i]
	if b not in dicplus:
		dicplus[b] = 1
	else:
		dicplus[b] += 1
	if c not in dicmins:
		dicmins[c] = 1
	else:
		dicmins[c] += 1

ans = 0
for i in dicplus:
	if i in dicmins:
		ans += dicplus[i] * dicmins[i]
print (ans)

Submission status: Accepted

Solution code:
s=i=0
d={}
for a in[*open(0)][1].split():a=int(a);s+=d.get(i-a,0);d[i+a]=d.get(i+a,0)+1;i+=1
print(s)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

print(ans)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
i=s=0
d=[0]*n
for a in a:
  if i>=a:s+=d[i-a]
  if i+a<n:d[i+a]+=1
  i+=1
print(s)

Submission status: Accepted

Solution code:
n = int(input())
A = list(map(int,input().split()))
idx = [i+1 for i in range(n)]
B = [i-j for i,j in zip(A, idx)]
C = [-(i+j) for i,j in zip(A, idx)]
looked = {}
ans = 0
for b,c in zip(B, C):
    if b in looked.keys():
        ans += looked[b]
    if c in looked.keys():
        looked[c] += 1
    else:
        looked[c] = 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**10
MOD = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))

minus = []
plus = []
for i in range(len(A)):
    minus.append(A[i]-(i+1))
    plus.append(A[i]+(i+1))

d = {}
for m in minus:
    d[m] = d.get(m,0) + 1

ans = 0
for p in plus:
    ans += d.get(-p,0)
print (ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())
s,*d=[0]*-~n
for i,a in enumerate(a):
  if i>=a:s+=d[i-a]
  if i+a<n:d[i+a]+=1
print(s)

Submission status: Accepted

Solution code:
# 常にi < jを考える
from collections import Counter

N = int(input())
H = [0]
H.extend(list(map(int, input().split())))

plus = [H[i] + i for i in range(1,N+1)]
minus = [i - H[i] for i in range(1, N+1)]
ans = 0

# 独立というのがよくわからなかったが，
# i > jで成り立つと仮定すると，
# aj -ai = Ai + Aj > 0　で，
# j > i となり，矛盾する。
# 連想配列で調べれば良い

cnt = Counter(minus)

for i in plus:
    ans += cnt.get(i, 0)

print(ans)

Submission status: Accepted

Solution code:
#  =========     /\       /|    |====/|
#      |        /  \       |    |   / |
#      |       /____\      |    |  /  |
#      |      /      \     |    | /   |
#  ========= /        \  =====  |/====|  
#  code

def main():
    from collections import defaultdict as dd
    d = dd(lambda : 0)
    n = int(input())
    a = list(map(int , input().split()))

    for idx , i in enumerate(a):
        d[idx + 1 - i] += 1
    
    cnt = 0
    for idx , i in enumerate(a):
        cnt += d[i + idx + 1]
    
    print(cnt)
    return

if __name__ == "__main__":
    main()

Submission status: Accepted

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

L = [None] * N
R = [None] * N
for i in range(N):
    L[i] = i + 1 + A[i]
    R[i] = i + 1 - A[i]

dl = dict()
dr = dict()
for l in L:
    dl[l] = dl.get(l, 0) + 1
for r in R:
    dr[r] = dr.get(r, 0) + 1

cnt = 0
for k in dl.keys():
    cnt += dl.get(k, 0) * dr.get(k, 0)

print(cnt)

Submission status: Accepted

Solution code:
import math
from collections import defaultdict
 
def readInt():
	return int(input())
def readInts():
	return list(map(int, input().split()))
def readChar():
	return input()
def readChars():
	return input().split()
def factorization(n):
	res = []
	if n%2==0:
		res.append(2)
	for i in range(3,math.floor(n//2)+1,2):
		if n%i==0:
			c = 0
			for j in res:
				if i%j==0:
					c=1
			if c==0:
				res.append(i)
	return res
def fact2(n):
	p = factorization(n)
	res = []
	for i in p:
		c=0
		z=n
		while 1:
			if z%i==0:
				c+=1
				z/=i
			else:
				break
		res.append([i,c])
	return res
def pop2(li):
	c=1
	i=li.pop(0)
	while 1:
		j=li.pop(0)
		if j==i:
			c+=1
		else:
			break
	return i,c,[j]+li

n = readInt()
a = readInts()

li = []
ri = []

d1 = defaultdict(int)
d2 = defaultdict(int)

for i in range(n):
	d1[i+a[i]]+=1
	d2[i-a[i]]+=1

ans = 0

for key in d1:
	ans+=d1[key]*d2[key]

print(ans)

Submission status: Accepted

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

l = {}
r = {}

for i in range(n):
    if i+a[i] in l.keys():
        l[i+a[i]] += 1
    else:
        l[i+a[i]] = 1
    if i-a[i] in r.keys():
        r[i-a[i]] += 1
    else:
        r[i-a[i]] = 1         

ans = 0
for i in l.keys():
    if i in r.keys():
        ans += l[i]*r[i]

print(ans)

Submission status: Accepted

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

import sys

def main():
    N = int(input())
    A = list(map(int, input().split()))
    dic_Lg = {}
    dic_Lw = {}
    for i in range(N):
        x = i - A[i]
        if x in dic_Lg:
            dic_Lg[x]+=1
        else:
            dic_Lg[x]=1
        y = i + A[i]
        if y in dic_Lw:
            dic_Lw[y]+=1
        else:
            dic_Lw[y]=1
    LP = list(dic_Lw.keys()) + list(dic_Lg.keys())
    LP = set(LP)
    ret = 0
    for i in LP:
        if i in dic_Lg and i in dic_Lw:
            ret += dic_Lg[i] * dic_Lw[i]
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import sys
from collections import Counter
from itertools import permutations, combinations
#from fractions import gcd
from math import gcd
from math import ceil, floor
import bisect
sys.setrecursionlimit(10 ** 6)
inf = float("inf")

def input():
    return sys.stdin.readline()[:-1]

def main():
    n = int(input())
    a = list(map(int, input().split()))
    d = {}
    ans = 0
    for i in range(n):
        if i+a[i] in d.keys():
            d[i+a[i]] += 1
        else:
            d[i+a[i]] = 1
    for i in range(n):
        if i - a[i] in d.keys():
            ans += d[i-a[i]]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]
H = defaultdict(int)
ans = 0
for i, v in enumerate(A):
    ans += H[i-v]
    H[i+v] += 1
print(ans)

Submission status: Accepted

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

import sys

from bisect import bisect_left, bisect_right

def main():
    N = int(input())
    A = list(map(int, input().split()))
    dic_Lg = {}
    for i in range(N):
        x = i - A[i]
        if x in dic_Lg:
            dic_Lg[x].append(i)
        else:
            dic_Lg[x]=[i]
    ret = 0
    for i in range(N):
        y = i+A[i]
        if not y in dic_Lg:
            continue
        arr = dic_Lg[y]
        r = bisect_right(arr, i)    # 5が入るべき境目のうち最も右側の境目を返す
        ret += len(arr)-r
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def is_ok(mid: int, target: int, ls: []):
    return target <= ls[mid]


def bi_search(target: int, ls: []):
    ng = -1
    ok = len(ls)

    cnt = 0
    while ok - ng > 1:
        mid = ng + int((ok - ng) / 2)
        cnt += 1
        if is_ok(mid, target, ls):
            ok = mid
        else:
            ng = mid
    return ok


def main():
    n = int(input())
    l_dic = {}
    r_dic = {}
    i = 0
    for a in map(int, input().split()):
        ld = l_dic.setdefault(i + a, [])
        ld.append(i)
        rd = r_dic.setdefault(i - a, [])
        rd.append(i)
        i += 1

    count = 0
    for rk, rv_list in r_dic.items():
        if rk not in l_dic:
            continue
        lv_list = l_dic[rk]
        for rv in rv_list:
            ind = bi_search(rv, lv_list)
            if ind == len(lv_list):
                count += ind
            else:
                count += ind + 1
            # for lv in lv_list:
            #     if lv < rv:
            #         count += 1
            #     else:
            #         break

    print(count)


main()

Submission status: Accepted

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


def rle(list):
    dict = {}
    for i in list:
        if i in dict.keys():
            dict[i] += 1
        else:
            dict[i] = 1
    return dict


n = int(input())
a = list(map(int, input().split()))
minus = rle([i-a[i] for i in range(n)])
plus = rle([i+a[i] for i in range(n)])

cnt = 0
for i in minus:
    if i in plus:
        cnt += minus[i] * plus[i]
print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
INF = 10**10
MOD = 10**9 + 7
N = int(input())
A = list(map(int,input().split()))

minus = []
plus = []
for i in range(len(A)):
    minus.append(A[i]-(i+1))
    plus.append(-A[i]-(i+1))

d = {}
for m in minus:
    d[m] = d.get(m,0) + 1

ans = 0
for p in plus:
    ans += d.get(p,0)
print (ans)

Submission status: Accepted

Solution code:
from collections import*
n,*a=map(int,open(0).read().split())
b,c,z=[],[],0
for i,q in enumerate(a):b+=i+q,;c+=i-q,
c=Counter(c)
for j,p in Counter(b).items():z+=p*c[j]
print(z)

Submission status: Accepted

Solution code:
#!python3

from collections import defaultdict

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    A = list(iim())

    ans = 0
    dp = [0]*N
    for i, ai in enumerate(A):
        x = i + ai
        if x < N:
            dp[x] += 1
        x = i - ai
        if x >= 0:
            ans += dp[x]

    print(ans)

if __name__ == "__main__":
    resolve()