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: Time Limit Exceeded

Solution code:
numOfAttendees = int(input())
attendeeHeight = list(map(int, input().split()))
count = 0

for i in range(0, numOfAttendees):
    temp = attendeeHeight[i]
    lowerBound = temp + i
    if lowerBound < numOfAttendees:
        for j in range(lowerBound, numOfAttendees):
            if attendeeHeight[j] < j:
                if temp + attendeeHeight[j] == j - i:
                    count += 1

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
cnt = 0
for i in range(n-1, 0, -1):
    x = i - a[i]
    if x < 0:
        continue
    for j in range(i-1, -1, -1):
        if j + a[j] == x:
            cnt += 1
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
height = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i+1, n):
        if(j-i == height[j] + height[i]):
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import heapq
n = int(input())
a = list(map(int, input().split()))
ind = 0
count = 0
for i in range(n-1):
    for j in range(i+1, n):
        if abs(i-j) == a[i]+a[j]:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())

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

cnt=0

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

Submission status: Time Limit Exceeded

Solution code:
d=int(input())
x=[int(w) for w in input().split()]
ans=0
for i in range(d-1):
    for j in range(i+1,d):
        if abs(i-j)==x[i]+x[j]:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

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

print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
hlist = list(map(int, input().split()))
alist = list(range(1, n+1))

ans = 0
# The absolute difference of their attendee numbers is equal to the sum of their heights.
for i, h1 in enumerate(hlist):
    for j, h2 in enumerate(hlist):
        if h2>n or h1>n or h1+h2>n:
            continue
        if abs(i-j) == h1+h2:
            ans += 1

print(ans//2)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
u=0
for i in range(1,N):
  for j in range(i+1,N+1):
    t=abs(i-j)
    if t==A[i-1]+A[j-1]:
      u+=1
print(u)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i,j in combinations(range(N), 2):
    if j-i == A[i]+A[j]:
        ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
A=list(map(int,input().split()))
u=0
for i in range(1,N):
  for j in range(i+1,N+1):
    t=abs(i-j)
    if t==A[i-1]+A[j-1]:
      u+=1
print(u)

Submission status: Time Limit Exceeded

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

cnt = 0
for n1 in range(N-1):
    for n2 in range(n1+1, N):
        f = A[n1] + A[n2] - n2 + n1
        if f==0:
            cnt+=1
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    count = 0

    for i in range(n - 2):
        for j in range(i + 2, n):
            num = j - i
            list_num = a[i] + a[j]
            if num == list_num:
                count += 1
    if count == 0:
        print(0)
    else:
        print(count)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a_list = list(map(int, input().split()))
cnt = 0
for num_1 in range(0,n):
    for num_2 in range(num_1+1, n):
        sum_height = a_list[num_1] + a_list[num_2]
        if sum_height == abs(num_1 - num_2):
            cnt += 1
            
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
a = list(map(int,input().strip().split()))[:n]
count=0
for i in range(n):
    for j in range(i+1,n):
        if(abs(i-j)==a[i]+a[j]):
            count+=1
            
print(count)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
numOfAttendees = int(input())
attendeeHeight = list(map(int, input().split()))
count = 0

for i in range(0, numOfAttendees):
    temp = attendeeHeight[i]
    lowerBound = temp + i
    if lowerBound < numOfAttendees:
        for j in range(lowerBound, numOfAttendees):
            if temp + attendeeHeight[j] == j - i:
                count += 1

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(N-1):
    for j in range(N-i-1):
        if A[j] + A[j+i+1] == i+1:
            ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    a = list(map(int, input().split()))
    count = 0

    for i in range(n - 1):
        for j in range(i + 1, n):
            num = j - i
            list_num = a[i] + a[j]
            if num == list_num:
                count += 1
    if count == 0:
        print(0)
    else:
        print(count)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
AP = [0]*N
AM = [0]*N

for i in range(N):
    AP[i]=i+A[i]
    AM[i]=i-A[i]

cnt=0
QC = Counter(AP)
for m in AM:
    cnt += QC[m]

print(cnt)

Submission status: Accepted

Solution code:
N = int(input())
A = [(int(x), i+1) for i, x in enumerate(input().split())]

def test(N, A):
    answer = 0
    for a0, i0 in A:
        for a1, i1 in A:
            if a1 + a0 == abs(i1 - i0):
                answer += 1
    return answer // 2

def solve(N, A):
    memo0 = {}
    memo1 = {}
    for a, n in A:
        k = - (a+n)
        if k not in memo0:
            memo0[k] = 0
        memo0[k]+=1
        k = n-a
        if k not in memo1:
            memo1[k] = 0
        memo1[k]+=1
    #print(f"{memo0=}")
    #print(f"{memo1=}")
    answer = 0
    for a, n in A:
        k = a - n
        if k in memo0:
            answer += memo0[k]
        k = a + n
        if k in memo1:
            answer += memo1[k]

    return answer // 2

#print(test(N, A))
print(solve(N, A))

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())

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

dic = defaultdict(int)

ans = 0

# j - aj = ai + iとして、jを固定して考える
# jを一つずつみていって、それまでに出会った物の中からj-ajに等しい物の数を数える。ai + iは記録しておく。
for i in range(len(a)):
    
    t = i - a[i]
    ans += dic[t]
    dic[a[i]+i] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
x=list(map(int,input().split()))
a=[]
b=[]
for i in range(n):
    a.append(x[i]+i+1)
    b.append((i+1)-x[i])
a,b=Counter(a),Counter(b)
ans=0
for i in range(n):
    ans+=a[i]*b[i]
print(ans)

Submission status: Accepted

Solution code:
# 参考 : https://atcoder.jp/contests/abc166/submissions/16829140
n = int(input())
a = list(map(int,input().split()))
# 参加者 i,j が取引する場合、 j - i = A_i + A_j が成り立つ。
# 変形すると -i - A_i = -j + A_j, i + A_i = j - A_j になる。
# l = i + A_i, r = j - A_j
l = [i + a[i] for i in range(n)]
r = [i - a[i] for i in range(n)]
# 連想配列(辞書)を使う。
x = {}
y = {}
# 辞書にキーを追加する。
for i in range(n):
    x[l[i]] = 0
    y[l[i]] = 0
    y[r[i]] = 0
# キーの値を人数分増やす。
for i in range(n):
    x[l[i]] += 1
    y[r[i]] += 1
ans = 0
# x のキーで取引する人数を調べる。
for i in set(x.keys()):
    ans += x[i] * y[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
#t:  1, 2, 3,..., N
#A: A1,A2,A3,...,AN
#|t-s| = At+As となるt,sのペアの数は、
# t-s  = At+As かつ t>s となるt,sのペアの数と等しく、
# t-At =  s+As かつ t>s となるt,sのペアの数と等しい
ms = [0]*N
ps = [0]*N
for i in range(N):
    ms[i],ps[i] = (i+1)-A[i],(i+1)+A[i]

msc,psc = {},{}
mi,pi = 0,0
out = 0
while mi<N:
    msc[ms[mi]] = msc.get(ms[mi],0)+1
    out += psc.get(ms[mi],0)
    psc[ps[mi]] = psc.get(ps[pi],0)+1
    mi+=1
    pi+=1
print(out)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    d = defaultdict(int)
    d2 = defaultdict(int)

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

    for i in range(N):
        d[i + 1 + A[i]] += 1
        d2[max(0, (i + 1) - A[i])] += 1

    ans = 0

    for k,v in d.items():
        if k == 0:continue
        ans += v * d2[k]

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
x = list(map(int, input().split()))
a = []
b = []
for i in range(n):
    a.append(i+1+x[i])
    b.append(i+1-x[i])
ans = 0
a, b = Counter(a), Counter(b)
for i in range(min(a), max(b)+1):
    ans += a[i]*b[i]
print(ans)

Submission status: Accepted

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

t = [0] * (N + 1)
ans = 0
for i in range(N):
    sa = i - A[i]
    if sa >= 0:
        ans += t[sa]
    wa = i + A[i]
    if wa < N:
        t[wa] += 1

print(ans)

Submission status: Accepted

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

from collections import defaultdict
dic = defaultdict(int)

ans = 0
for i in range(n):
  if i - A[i] in dic:
    ans += dic[i-A[i]]
  dic[i+A[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
# import itertools
# import math
# import sys
# sys.setrecursionlimit(500*500)
# import numpy as np
# import heapq
# from collections import deque

N = int(input())
# S = input()
# n, *a = map(int, open(0))
# N, M = map(int, input().split())
A = list(map(int, input().split()))
# B = list(map(int, input().split()))
# tree = [[] for _ in range(N + 1)]
# B_C = [list(map(int,input().split())) for _ in range(M)]
# S = input()

# B_C = sorted(B_C, reverse=True, key=lambda x:x[1])
# all_cases = list(itertools.permutations(P))
# a = list(itertools.combinations_with_replacement(range(1, M + 1), N))
# itertools.product((0,1), repeat=n)

# A = np.array(A)
# cum_A = np.cumsum(A)
# cum_A = np.insert(cum_A, 0, 0)

# def dfs(tree, s):
#     for l in tree[s]:
#         if depth[l[0]] == -1:
#             depth[l[0]] = depth[s] + l[1]
#             dfs(tree, l[0])
# dfs(tree, 1)

# def factorization(n):
#     arr = []
#     temp = n
#     for i in range(2, int(-(-n**0.5//1))+1):
#         if temp%i==0:
#             cnt=0
#             while temp%i==0:
#                 cnt+=1
#                 temp //= i
#             arr.append([i, cnt])
#     if temp!=1:
#         arr.append([temp, 1])
#     if arr==[]:
#         arr.append([n, 1])
#     return arr
A.insert(0, 0)
cnt = [0] * (N + 1)
ans = 0
for i in range(1, N + 1):
    if i - A[i] >= 0:
        ans += cnt[i - A[i]]
    if i + A[i] <= N:
        cnt[i + A[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N = int(input())
As = list(mapint())

plus = [i+a for i, a in enumerate(As)]
minus = [i-a for i, a in enumerate(As)]
from collections import Counter

pc = Counter(plus)
mc = Counter(minus)
ans = 0
for p, cnt in pc.most_common():
    ans += cnt*mc[p]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [i+a[i] for i in range(n)]
r = [i-a[i] for i in range(n)]
lc = {}
rc = {}
for i in range(n):
    lc[l[i]] = 0
    lc[r[i]] = 0
    rc[r[i]] = 0
    rc[l[i]] = 0
for i in range(n):
    lc[l[i]] += 1
    rc[r[i]] += 1
ans = 0
for i in set(lc.keys()):
    ans += rc[i]*lc[i]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
As = list(map(int,input().split()))
dic = {}
array = []
x = As[0]
init = 1 - x
for i in range(1,N):
    v = init + i - 1 - As[i]
    array.append(v)
    if v not in dic:
        dic[v] = 1
    else:
        dic[v] += 1
if 0 in dic:
    ans = dic[0]
else:
    ans = 0

for i in range(1,N):
    y = As[i] + i - x
    z = array[i-1]
    dic[z] -= 1
    if y in dic:
        ans += dic[y]
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
num1=[0]*(2*(10**5)+10)
num2=[0]*(2*(10**5)+10)
for i in range(n):
    if a[i]+i+1<2*(10**5)+5:
        num1[a[i]+i+1]+=1
    if a[i]+1<i+1:
        num2[-a[i]+i+1]+=1
ans=0
for i in range(len(num1)):
    ans+=num1[i]*num2[i]
print(ans)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.buffer.readline


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


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


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))


# rstrip().decode('utf-8')

from collections import defaultdict

def main():
	n=II()
	A=LI()
	
	X=defaultdict(int)
	Y=defaultdict(int)
	
	for i,v in enumerate(A):
		X[i+v]+=1
		Y[i-v]+=1
	
	ans=0
	for k,v in X.items():
		ans+=v*Y[k]
	print(ans)
	
	







if __name__=="__main__":
	main()

Submission status: Accepted

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


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


def input_int():
    return int(input())


def input_int_list():
    return [int(i) for i in input().split()]


def main():
    n = input_int()
    A = [None] + input_int_list()
    ans = 0
    d = defaultdict(int)
    # i < j とすると、
    # j - i = Ai + Aj
    # Ai + i = j - Aj となる
    # 列の後ろから評価し、条件を満たす個数を足していけば良い
    # 計算量：O(n)
    for i in range(n, 0, -1):
        cur = i + A[i]
        ans += d[cur]
        d[i - A[i]] += 1
    print(ans)

    return


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math , sys

N  = int( input() )

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

def Prime(x):
    ub=int(math.sqrt(x))+2
    if x==2 or x==3 or x==5 or x==7:
        return True
    for i in range(2,ub):
        if x%i==0:
            return False
    return True

y = N
while not Prime(y):
    y+=1

def h1(x):
    return x % y
def h2(x):
    return 1+ x%(y-1)
def h(x,i):
    return (h1(x) + i*h2(x)) % y

def insert(T,x):
    i=0
    while True:
        j=h(x,i)
        if T[j][0]== -1:
            T[j][0]=x
            T[j][1]=1
            return j
        elif x ==T[j][0]:
            T[j][1]+=1
            return j
        else:
            i+=1

def search(T,x):
    i=0
    while True:
        j=h(x,i)
        if T[j][0] == x:
            return T[j][1]
        elif T[j][0] == -1:
            return -1
        else:
            i+=1

T = [[-1,0] for _ in range(y)]
for i in range(N):
    insert(T , i + A[i])
ans =0
        
for j in range(N):
    if j - A[j]>=0:
        s = search(T, j - A[j])
        if s >=0:
            ans+=s
print(ans)

Submission status: Accepted

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

l=[]
r=[]

for i in range(n):
  nu=i+1
  x=a[i]
  l.append(x+nu)
  r.append(nu-x)
  
di1={}
di2={}

for i in range(0,n):
  if i==n-1:
    continue
  else:
    if l[i] not in di1:
      di1[l[i]]=0
    di1[l[i]]+=1
    if r[i+1] not in di2:
      di2[r[i+1]]=0
    di2[r[i+1]]+=1
    if r[i+1] in di1:
      ans+=di1[r[i+1]]
      
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

L, R = Counter(L), Counter(R)

ans = 0

for k in L.keys():
    ans += L[k] * R[k]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
B = [a+i for i, a in enumerate(A)]
C = [j-a for j, a in enumerate(A)]
B, C = Counter(B), Counter(C)
ans = 0
for k in B.keys():
    ans += B[k]*C[k]
print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
plus=[]
minus=[]
for i in range(N):
  plus.append(A[i]+i+1)
  minus.append(-A[i]+i+1)
from collections import Counter
p=Counter(plus)
m=Counter(minus)
sp=set()
for k in p.keys():
  sp.add(k)
ans=0
for k,v in m.items():
  if k in sp:
    ans+=v*p[k]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

A = [i + n for i, n in enumerate(nums, start=1)]
B = [j - n for j, n in enumerate(nums, start=1)]
BC = Counter(B)
answer = 0
for a in A:
  answer += BC[a]
print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict

N = int(input())
A = list(map(int, input().split()))
Ai = [(i + 1) - a for i, a in enumerate(A)]
Aj = [(j + 1) + a for j, a in enumerate(A)]
cntAi = defaultdict(lambda: 0)
for ai in Ai:
    cntAi[ai] += 1

ans = 0
for ai, aj in zip(Ai, Aj):
    cntAi[ai] -= 1
    ans += cntAi[aj]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())

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

dic = defaultdict(int)

ans = 0

for i in range(N):
    t = i - A[i]
    ans += dic[t]
    dic[i+A[i]] += 1

print(ans)

Submission status: Accepted

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

d={}

for i in range(len(A)):
  d.setdefault(i-A[i],0)
  d[i-A[i]]+=1
ans=0
for i in range(len(A)):
  if d.get(i+A[i]):
    ans+=d.get(i+A[i])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
constS = defaultdict(int)
constD = defaultdict(int)
for i in range(N):
    Ss = i + A[i]
    Dd = i - A[i]
    constS[Ss] += 1
    constD[Dd] += 1
ans = 0
for key,val in constS.items():
    ans += val * constD[key]
print(ans)

Submission status: Accepted

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

p = [0] * N
m = [0] * N

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

from collections import Counter

cp = Counter(p)
cm = Counter(m)

ans = 0

for x, y in cp.items():
    ans += cm[x] * y

print(ans)

Submission status: Accepted

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

plus=[0]*1000000
minus=[0]*1000000

for i in range(n):
  ene=i+1
  pin=a[i]
  pl,mi=ene+pin,ene-pin
  if 0<=pl<1000000:
    plus[pl]+=1
  if 0<=mi<1000000:
    minus[mi]+=1
  
for i in range(1000000):
  ans+=plus[i]*minus[i]
  

print(ans)

Submission status: Accepted

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

b = [0 for i in range(n)]

cnt = 0
for i in range(n):
    if i - a[i] >= 0:
        cnt += b[i - a[i]]
    if i + a[i] < n:
        b[i + a[i]] += 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
import numpy as np
import collections

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

B = defaultdict(int)

ans = 0

for index, A in enumerate(As):
    ans += B[index-A]
    
    B[index+A] += 1
#    print(B)
#    print(list(B[:20]))

print(ans)

Submission status: Accepted

Solution code:
# ABC166 
from collections import Counter

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

Ai=[]
Aj=[]

for i in range(1,N+1):
    Ai.append(i+A[i])
    Aj.append(i-A[i])
    
ci=Counter(Ai).items()
cj=Counter(Aj)
res=0
for c,n in ci:
    m=cj[c]
    res+=m*n
print(res)

Submission status: Accepted

Solution code:
n=int(input())
a=[int(x) for x in input().split()]

dic1={}
dic2={}
for i in range(n):
  if i+1+a[i] not in dic1:
    dic1[i+1+a[i]]=1
  else:
    dic1[i+1+a[i]]+=1

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

ans=0

for i in dic1:
  if i not in dic2:
    continue

  ans+=dic1[i]*dic2[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

# j-i == A[i]+A[j] (i < j)                                                                                                                                                                                                                    
# A[i]+i == j-A[j]                                                                                                                                                                                                                            

memo = defaultdict(int)

ans = 0
for i in range(N):
    target = i - A[i]
    ans += memo[target]
    memo[A[i]+i] += 1
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
p=[]
m=[]
for i in range(n):
    p.append(i+a[i])
    m.append(i-a[i])
x=[0]*(2*n)
y=[0]*(2*n)
ans=0
for i in range(n):
    if 0<=p[i]<=(2*n)-1:
        x[p[i]]+=1
    if 0<=m[i]<=(2*n)-1:
        y[m[i]]+=1
for i in range(n):
    ans+=x[i]*y[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

left = [i+A[i] for i in range(n)]
right = [i-A[i] for i in range(n)]

r_counter = Counter(right)

ans = 0

for l in left:
    ans += r_counter[l]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
Alist = list(map(int,input().split()))
Aplu = []
Amin = dict()
for i in range(N):
    A = Alist[i]
    Aplu.append(A+(i+1))
    if (i+1)-A not in Amin:
        Amin[(i+1)-A] = 1
    else:
        Amin[(i+1)-A] += 1
Answer = 0
for k in Aplu:
    if k in Amin:
        Answer += Amin[k]
print(Answer)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

N = int(input())

A = list(map(int, input().split()))
Ap = [i - A[i] for i in range(N)]
Ap.sort()

ans = 0
for i in range(N):
	ans += bisect_right(Ap, i + A[i]) - bisect_left(Ap, i + A[i])

print(ans)

Submission status: Accepted

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

num = {}
ans = 0
for i, v in enumerate(A):
    p = v+i
    m = i-v
    if p not in num:
        num[p] = 1
    else:
        num[p] += 1
    if m in num:
        ans += num[m]
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import Counter

N = int(input())
A = list(map(int, sys.stdin.readline().rsplit()))

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

res = 0
C = Counter(Q)
for p in P:
    res += C[p]

print(res)

Submission status: Accepted

Solution code:
def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    L = [i+A[i-1] for i in range(1,N+1)]
    R = [i-A[i-1] for i in range(1,N+1)]
    import collections
    Lcnter = collections.Counter(L)
    Rcnter = collections.Counter(R)
    values = set(Lcnter.keys()) & set(Rcnter.keys())
    ans = 0
    for i in values:
        ans += Lcnter[i]*Rcnter[i]
    print(ans)
    


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n = int(input())
a = [int(i) for i in input().split()]

j_Aj = [0]

for j, aj in enumerate(a):
    j_Aj.append(j + 1 - aj)
maxj=max(j_Aj)
i_Ai = [0] * (maxj+1)
ans = 0
for j, j_aj in enumerate(j_Aj):
    if j == 0:
        continue
    if j_aj >= 2:
        ans += i_Ai[j_aj]
    if j + a[j - 1]<=maxj:
        i_Ai[j + a[j - 1]] += 1
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = dict()
ans = 0

for i in range(n):
    num[i+a[i]] = 0
    
for i in range(n):
    num[i+a[i]] += 1
    
for i in range(n):
    if i-a[i] in num:
        ans += num[i-a[i]]
        
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
num = dict()
ans = 0

for i in range(n):
    num[i+a[i]] = 0

for i in range(n):
    if i-a[i] in num:
        ans += num[i-a[i]]
    num[i+a[i]] += 1
print(ans)

Submission status: Accepted

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

counter = {}

for i in range(N):
    counter[i + A[i]] = 0

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

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
lst = [int(i) for i in input().split()]

dic = {}
count = 0
for i in range(n):
  num = lst[i]
  a = i + num
  if a not in dic:
    dic[a] = 1
  else:
    dic[a] += 1
  b = i - num
  if b in dic:
    count += dic[b]
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

maxVal = N + max(A)
ans = 0

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

candidatesR = defaultdict(int)
for j in range(1, N+1):
    candidatesR[j-A[j-1]] += 1

ans = 0
for x in candidatesL.keys():
    ans += candidatesL[x] * candidatesR[x]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
y=list(map(int,input().split()))
from collections import Counter
lhs=Counter([j+y[j] for j in range(n)])
rhs=Counter([j-y[j] for j in range(n)])
count=0
for i in lhs:
   if i in rhs:
      count+=lhs[i]*rhs[i]

print(count)

Submission status: Accepted

Solution code:
import sys
import collections

input_methods=['clipboard','file','key']
using_method=0
input_method=input_methods[using_method]

tin=lambda : map(int, input().split())
lin=lambda : list(tin())
mod=1000000007

#+++++

def main():
	n = int(input())
	#b , c = tin()
	#s = input()
	al = lin()
	aal=[i-v for i,v in enumerate(al)]
	ccl = collections.Counter(aal)
	ret = 0
	
	for i, v in enumerate(al):
		ccl[i-v] -= 1
		if i+v in ccl:
			ret += ccl[i+v]
		
	print(ret)
		
	
	
#+++++
isTest=False

def pa(v):
	if isTest:
		print(v)
		
def input_clipboard():
	import clipboard
	input_text=clipboard.get()
	input_l=input_text.splitlines()
	for l in input_l:
		yield l

if __name__ == "__main__":
	if sys.platform =='ios':
		if input_method==input_methods[0]:
			ic=input_clipboard()
			input = lambda : ic.__next__()
		elif input_method==input_methods[1]:
			sys.stdin=open('inputFile.txt')
		else:
			pass
		isTest=True
	else:
		pass
		#input = sys.stdin.readline
			
	ret = main()
	if ret is not None:
		print(ret)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = [0] + list(map(int,input().split()))

a_pos = [a[i]+i for i in range(1,n+1)]
a_neg = [-a[i]+i for i in range(1,n+1)]
#print(a_pos)
#print(a_neg)

c_pos = collections.Counter(a_pos)
c_neg = collections.Counter(a_neg)
#print(c_pos)
#print(c_neg)

ans = 0
for c in c_pos:
    ans += c_pos[c] * c_neg[c]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
jc=[0]*n
for i in range(n):
    jc[i]+=i+1-a[i]
jcc=Counter(jc)
count=0
for j in range(n):
    count+=jcc[a[j]+j+1]
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import collections as cl
import sys


def II():
    return int(sys.stdin.readline())


def MI():
    return map(int, sys.stdin.readline().split())


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


def main():
    N = II()
    A = LI()

    counter_add = cl.Counter()
    counter_sub = cl.Counter()
    for i in range(N):
        add = i + 1 + A[i]
        sub = i + 1 - A[i]
        counter_add.update({str(add): 1})
        counter_sub.update({str(sub): 1})

    ans = 0
    for key, val in counter_add.items():
        ans += val * counter_sub[key]

    print(ans)


main()

Submission status: Accepted

Solution code:
from collections import Counter

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

A_pos = [A[x]+x for x in range(n)]
A_neg = [-A[x]+x for x in range(n)]

C_pos = Counter(A_pos)
C_neg = Counter(A_neg)

ans = 0

for c in C_pos:
    ans += C_pos[c] * C_neg[c]
print(ans)

Submission status: Accepted

Solution code:
from sys import stdin,stdout
# n,e=list(map(int,stdin.readline().split()))
n=int(stdin.readline())
a=list(map(int,stdin.readline().split()))
d={};ans=0
for i in range(n):
    d[a[i]+i]=d.get(a[i]+i,0)+1
for i in range(n):
    ans+=d.get(i-a[i],0)
print(ans)