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:
#!python3

from collections import defaultdict

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

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

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

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

    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

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

ans = 0
for d in d1:
    if d in d2:
        ans += (d1[d] * d2[d])
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d = defaultdict(int)
ans = 0

for i, a in enumerate(A_list, 1):
    d[i+a] += 1

for i, a in enumerate(A_list, 1):
    ans += d[i-a]

print(ans)

Submission status: Accepted

Solution code:
delta = {}

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

for i, e in enumerate(a):
    delta[i - e] = delta.get(i - e, 0) + 1

for i, e in enumerate(a):
    k += delta.get(e + i, 0)

print(k)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
a = [int(i) for i in input().split()]
from collections import Counter
c = Counter([])
ans = 0
for i,ai in enumerate(a):
  S = i+1+ai
  if i > 0:
    L = i+1-ai
    if L in c:
      ans += c[L]
  c.update({S:1})
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# E - This Message Will Self-Destruct in 5s
from collections import defaultdict


def main():
    N, *A = map(int, open(0).read().split())
    cnt = defaultdict(int)
    ans = 0
    for i, a in enumerate(A, 1):
        cnt[i + a] += 1
        ans += cnt[i - a]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
li1=[0]*n
li2=[0]*n
for i in range(n):
    li1[i] = i + a[i]
    li2[i] = i - a[i]

li1.sort()
li2.sort()
l1=l2=0

ans = 0

while 1:
    if li1[l1] == li2[l2]:
        cnt1=cnt2=1
        while  l1 < n-1 and li1[l1] == li1[l1+1]:
            l1 += 1
            cnt1 += 1
        while  l2 < n-1 and li2[l2] == li2[l2+1]:
            l2 += 1
            cnt2 += 1
        ans += cnt1*cnt2
        l1+=1
        l2+=1
    elif li1[l1] < li2[l2]:
        l1+=1
    else:
        l2+=1
    if l1 == n or l2 == n or (l1==l2==n-1):
        break
print(ans)

Submission status: Accepted

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

d = [0] * n

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

Submission status: Accepted

Solution code:
N = int(input())
A = [int(x) for x in input().split()]
res = {}
count = 0
for i in range(N):
  L = i+1 + A[i]
  res[L] = res.get(L,0) + 1
for i in range(N):
  R = i+1 - A[i]
  count = res.get(R,0) + count
print(count)

Submission status: Accepted

Solution code:
# a_i + a_j = j-i
# a_i + i = j - a_j
# a[i]+i = i -a[i]となることはない

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

ilis=[0]*n
jlis=[0]*n

for i in range(n):
  ilis[i]=a[i]+i
  jlis[i]=i-a[i]

from collections import defaultdict
idic=defaultdict(int)
jdic=defaultdict(int)
for i in range(n):
  idic[ilis[i]]+=1
  jdic[jlis[i]]+=1

ans=0
for item in idic.items():
  ans+=item[1] * jdic[item[0]]

print(ans)

Submission status: Accepted

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

r = 0
for i, a in enumerate(A):
    t = A_j.get(a + i)
    if t:
        r += t

print(r)

Submission status: Accepted

Solution code:
N = int(input())
arr = list(map(int,input().split()))
cnt_arr = [0]*N
ans = 0
for i in range(N):
  if arr[i]+i+1<N:
    cnt_arr[arr[i]+i+1] += 1
  if i+1-arr[i]>0:
    ans += cnt_arr[i+1-arr[i]]

print(ans)

Submission status: Accepted

Solution code:

from collections import Counter

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

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

Submission status: Accepted

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

ans = 0

R = []
for i ,Ai in enumerate(A,1):
  R.append(i+Ai)
R.sort()

L = []
for j ,Aj in enumerate(A,1):
  L.append(j-Aj)
L.sort()

for i in range(len(R)):
  r = bisect.bisect_right(L,R[i])
  l = bisect.bisect_left(L,R[i])
  ans+=r-l
 
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from copy import deepcopy

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


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

    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import Counter

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

Submission status: Accepted

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

wa = {}
ans = 0
for i in range(len(a)):
    temp_wa = (i + 1) + a[i]
    if temp_wa in wa.keys():
        wa[temp_wa]+=1
    else:
        wa[temp_wa] = 1

    temp_sa = (i+1) - a[i]
    if temp_sa in wa.keys():
        ans += wa[temp_sa]

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# 整数の入力
n = int(input())
h_list = input().split()
h_list = [int(h) for h in h_list]

count = 0
result_dict = {}

for i in range(n):
    key = (i+1) + h_list[i]
    value = result_dict.get(key, 0)
    result_dict[key] = value + 1

for j in range(n):
    key = (j+1) - h_list[j]
    count += result_dict.get(key, 0)

print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))
sa = []
st = []
for i in range(n):
  sa.append(a[i] + i)
  st.append(i - a[i])
c = defaultdict(int)
c = Counter(st)
sum = 0
for i in range(n-1):
  sum = sum + c[sa[i]]
print(sum)

Submission status: Accepted

Solution code:
from collections import Counter

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

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Y = [int(i + A[i - 1]) for i in range(1, N + 1)]
Y = Counter(Y)

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

Submission status: Accepted

Solution code:
import bisect

n = int(input())
a = list(map(int, input().split()))
x = [i + 1 + a[i] for i in range(n)]
y = [i + 1 - a[i] for i in range(n)]
x.sort()
ans = 0
for i in y:
    ans += (bisect.bisect_right(x, i) - bisect.bisect_left(x, i))
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import Counter

n, *a = map(int, sys.stdin.read().split())

def main():
    cb = Counter(a[i] + i for i in range(n))
    cc = Counter(j - a[j] for j in range(n))
    tot = 0
    for v, c in cb.items():
        tot += c * cc[v]
    print(tot)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

for j,a in enumerate(A):
    ans += dic[j-a]

print(ans)

Submission status: Accepted

Solution code:
def main():
 n,a=int(input()),list(map(int, input().split()));d,s=[0]*n,0
 for i,x in enumerate(a):
  if i+x<n:d[i+x]+=1
  if i-x>=0:s+=d[i-x]
 print(s)
main()

Submission status: Accepted

Solution code:
import sys
from collections import Counter

n, *a = map(int, sys.stdin.read().split())

def main():
    b = [a[i] + i for i in range(n)]
    c = [i - a[i] for i in range(n)]
    cb = Counter(b)
    cc = Counter(c)
    tot = 0
    for v, c in cb.items():
        tot += c * cc[v]
    print(tot)
    
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

plus = [0] * (N-1)
for i in range(N-1):
  plus[i] = i + A[i]

minus = [0] * (N-1)
for j in range(1, N):
  minus[j-1] = j - A[j]

sum = 0
c = dict(collections.Counter(minus))
for i in range(N-1):
  sum += c.get(plus[i], 0)
  c[minus[i]] -= 1

print(sum)

Submission status: Accepted

Solution code:
n,a=int(input()),list(map(int, input().split()))
d=[0]*n
def main():
 for i,x in enumerate(a):
  if i+x<n:d[i+x]+=1
 print(sum([d[i-x]for i,x in enumerate(a)if i-x>=0]))
main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)  # 再帰関数の再帰の深さを設定
to_index = lambda x: int(x) - 1  # 入力した数字に1を引いたものを返す
print_list_in_2D = lambda x: print(*x, sep="\n")  # リストの要素を改行を挟んで表示する関数

# 入力を整数に変換して受け取る
def input_int():
    return int(input())

def map_int_input():
    return map(int, input())

MII = map_int_input

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

def MII_to_index():
    return map(to_index, input())

def MII_split_to_index():
    return map(to_index, input().split())

# 入力全てを整数に変換したものの配列を受け取る
def list_int_inputs():
    return list(map(int, input()))

LII = list_int_inputs

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

# 2次元リスト化
def LII_2D(rows_number):
    return [LII() for _ in range(rows_number)]

def LII_split_2D(rows_number):
    return [LII_split() for _ in range(rows_number)]

N = input_int()
As = LII_split()

count = 0
ps = dict()
ms = dict()
for i in range(N):
    p = i + 1 + As[i]
    if p in ps:
        ps[p].append(i)
    else:
        ps[p] = [i]
    m = i + 1 - As[i]
    if m in ms:
        ms[m].append(i)
    else:
        ms[m] = [i]


for m, m_indicies in ms.items():
    if m not in ps:
        continue
    else:
        p_indicies = ps[m]
        count += len(p_indicies) * len(m_indicies)

print(count)

Submission status: Accepted

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

"""ナイーブ
count = 0
for i in range(n-1):
    for j in range(i, n):
        if i != j and abs(i-j) == a[i] + a[j]:
            count += 1
print(count)
"""
# idxとa[idx]で別々にループ回すからO(n**2)になってしまう
# 前処理としてidxとa[idx]の二つの情報をまとめた何かがつくれれば、、ってとこまでは気付けた
from collections import Counter
a_plus = [0]*n
a_minus = [0]*n
for i in range(n):
    a_plus[i] = i + a[i]
    a_minus[i] = i - a[i]
c1 = Counter(a_plus)
c2 = Counter(a_minus)
#print(c1)
#print(c2)
ans = 0
for key in c1.keys():
    if key in c2.keys():
        ans += c1[key]*c2[key]
print(ans)

Submission status: Accepted

Solution code:
def main():
 n,a=int(input()),list(map(int, input().split()))
 d=[0]*n
 for i,x in enumerate(a):
  if i+x<n:d[i+x]+=1
 print(sum([d[i-x]for i,x in enumerate(a)if i-x>=0]))
main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import Counter


def get_result(data):
    N = data[0][0]
    A = data[1]
    L = [0 for _ in range(N)]
    R = [0 for _ in range(N)]
    for i in range(N):
        L[i] = i + A[i] + 1
        R[i] = i + 1 - A[i]

    L_cnt = Counter(L)
    R_cnt = Counter(R)
    ans = 0
    all_key = list(set(R_cnt.keys() & L_cnt.keys()))
    for key in all_key:
        ans += L_cnt[key] * R_cnt[key]
    return ans


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
c = Counter()
ans = 0
for i, a in enumerate(map(int, input().split())):
    ans += c[i - a]
    c[a + i] += 1
print(ans)

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-

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

    Ldic = {}
    for i, a in enumerate(As):
        if not (a+i) in Ldic:
            Ldic[a+i] = 0
        Ldic[a+i] += 1

    ans = 0
    for j, a in enumerate(As):
        if j-a in Ldic:
            ans += Ldic[j-a]

    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
def main():
 n,a = int(input()),list(map(int, input().split()))
 d = [0]*n
 for i,x in enumerate(a):
  if i+x<n:d[i+x]+=1
 print(sum([d[i-x]for i,x in enumerate(a)if i-x>=0]))
main()

Submission status: Accepted

Solution code:
from sys import stdin
from collections import Counter


def get_result(data):
    N = data[0][0]
    A = data[1]
    L = [0 for _ in range(N)]
    R = [0 for _ in range(N)]
    for i in range(N):
        L[i] = i + A[i] + 1
        R[i] = i + 1 - A[i]

    L_cnt = Counter(L)
    R_cnt = Counter(R)
    ans = 0
    max_key = max(R_cnt.keys())
    for i in range(max_key+1):
        ans += L_cnt[i] * R_cnt[i]
    return ans


if __name__ == '__main__':
    raw_data = [val.rstrip() for val in stdin.readlines()]
    data = [list(map(int, val.split(' '))) for val in raw_data]
    result = get_result(data)
    print(result)

Submission status: Accepted

Solution code:
def main():
 n,a = int(input()),list(map(int, input().split()))
 d = [0]*n
 for i,x in enumerate(a):
  if i+x<n:d[i+x] += 1
 print(sum([d[i-x]for i,x in enumerate(a)if i-x>=0]))
main()

Submission status: Accepted

Solution code:
"""
import random
import functools
import copy
import bisect
import array
import re
import collections
import heapq
import fractions
import itertools
import string
import math
from operator import itemgetter as ig
from bisect import bisect_left, bisect_right, insort_left, insort_right
from itertools import permutations, combinations, product, accumulate, groupby
from heapq import heappush, heappop
from collections import deque, defaultdict, Counter
import sys
sys.setrecursionlimit(10 ** 7)
# import numpy as np

inf = 10 ** 20
INF = float("INF")
mod = 10 ** 9 + 7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = dd + [(-1, 1), (1, 1), (1, -1), (-1, -1)]
ddn9 = ddn + [(0, 0)]
'''for dx, dy in dd:
        nx = j + dx; ny = i + dy
            if 0 <= nx < w and 0 <= ny < h:'''
"""

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 7)


def wi(): return list(map(int, sys.stdin.readline().split()))
# WideIntPoint


def wip(): return [int(x) - 1 for x in sys.stdin.readline().split()]


def ws(): return sys.stdin.readline().split()


def si(): return int(sys.stdin.readline())  # SingleInt


def ss(): return input()


def hi(n): return [si() for _ in range(n)]


def hs(n): return [ss() for _ in range(n)]  # HeightString


def s_list(): return list(input())


def mi(n): return [wi() for _ in range(n)]  # MatrixInt


def mip(n): return [wip() for _ in range(n)]


def ms(n): return [ws() for _ in range(n)]


def num_grid(n): return [[int(i) for i in sys.stdin.readline().split()[
    0]] for _ in range(n)]  # NumberGrid


def grid(n): return [s_list() for _ in range(n)]


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


def round_up(a, b):
    """ a/b の切り上げ """
    c = (a + b - 1) / b
    return c


def lcm(a, b):
    """a,bの最小公倍数"""
    return a * b // gcd(a, b)


def floor(a, b):
    """floor(a/b) 整数値を返す"""
    c = (a - a % b)/b
    return int(c)


def main():
    n = int(input())
    a = wi()
    L = defaultdict(int)
    R = defaultdict(int)
    for i in range(n):
        L[i + a[i]] += 1
        R[i - a[i]] += 1
    ans = 0
    for i in L:
        ans += L[i] * R[i]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
r=[0]*(n-1)
t=[0]*(n)
dr={}
dt={l[0]:[0]}
for i in range(1,n):
  x=i-l[i]
  y=i+l[i]
  if x in dr:
    dr[x].append(i)
  else:
    dr[x]=[i]
  if y in dt:
    dt[y].append(i)
  else:
    dt[y]=[i]
ans=0
for x in dr.keys():
  if x>0 and x in dt:
    y=dr[x]
    z=dt[x]
    ans+=len(z)*len(y)
print(ans)

Submission status: Accepted

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

cnt_ind_minus_height = {}
cnt_height_plus_ind = {}
cnt_height_minus_ind = {}
cnt_minus_height_minus_ind = {}

for ind in range(n):
    height = hlist[ind]
    if ind - height not in cnt_ind_minus_height:
        cnt_ind_minus_height[ind - height] = 0
    cnt_ind_minus_height[ind - height] += 1

    if ind + height not in cnt_height_plus_ind:
        cnt_height_plus_ind[ind + height] = 0
    cnt_height_plus_ind[ind + height] += 1

    if height-ind not in cnt_height_minus_ind:
        cnt_height_minus_ind[height-ind] = 0
    cnt_height_minus_ind[height-ind] += 1

    if -ind - height not in cnt_minus_height_minus_ind:
        cnt_minus_height_minus_ind[-height-ind] = 0
    cnt_minus_height_minus_ind[-height-ind] += 1

ans = 0
# Hi - i = - (Hj + j)
for val in cnt_height_minus_ind:
    if val in cnt_minus_height_minus_ind:
        ans += cnt_height_minus_ind[val]*cnt_minus_height_minus_ind[val]

# Hi + i = j - Hj
for val in cnt_height_plus_ind:
    if val in cnt_ind_minus_height:
        ans += cnt_height_plus_ind[val]*cnt_ind_minus_height[val]

# as we double count the pair
print(ans//2)

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  a = list(map(int, input().split()))
  d = [0]*n
  for i, x in enumerate(a):
    if i+x < n: d[i+x] += 1
  print(sum([d[i-x] for i, x in enumerate(a) if i-x >= 0]))
main()

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
D={}
E={}
for i in range(N):
  a=i+A[i]
  b=i-A[i]
  D.setdefault(a,0)
  E.setdefault(b,0)
  D[a]+=1
  E[b]+=1
ans=0
for i in D.keys():
  if i in E.keys():
    ans+=D[i]*E[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  a = list(map(int, input().split()))
  d = [0]*n
  for i, x in enumerate(a):
    if i+x < n: d[i+x] += 1
  ans = 0
  for i, x in enumerate(a):
    if i-x >= 0: ans += d[i-x]
  print(ans)

if __name__ == "__main__":
  main()

Submission status: Accepted

Solution code:
def main():
  n = int(input())
  a = list(map(int, input().split()))
  d = [0]*n
  for i, x in enumerate(a):
    if i+x < n: d[i+x] += 1
  ans = 0
  for i, x in enumerate(a):
    if i-x >= 0: ans += d[i-x]
  print(ans)
main()

Submission status: Accepted

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

b = Counter(r)
for i in l:
    ans += b.get(i,0)
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import bisect


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    negA = []
    for i, a in enumerate(A):
        negA.append(i - a)

    cnt_negA = Counter(negA)
    negA_keys = sorted(cnt_negA.keys())
    ans = 0
    for i in range(N):
        if i + A[i] in cnt_negA:
            ans += cnt_negA[i + A[i]]
    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
import bisect


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    negA = []
    idx_negA = []
    for i, a in enumerate(A):
        negA.append(i - a)
        idx_negA.append(i)

    cnt_negA = Counter(negA)
    negA_keys = sorted(cnt_negA.keys())
    ans = 0
    for i in range(N):
        if i + A[i] in cnt_negA:
            ans += cnt_negA[i + A[i]]
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

N = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().strip().split()))
 
d = [0]*N
ans = 0
for i in range(N):
    a = A[i]
    l,r = i+a, i-a
    if 0 <= l < N:
        d[l] += 1
    if 0 <= r < N:
        ans += d[r]
 
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

    lst1 = [0] * n
    lst2 = [0] * n

    for i in range(1, n+1):
        p = i - a[i-1]
        q = i + a[i-1]

        if 0 <= p < n:
            lst1[p] += 1
        if 0 <= q < n:
            lst2[q] += 1

    for i in range(n):
        cnt += lst1[i] * lst2[i]

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import collections

if __name__ == "__main__":
    N = int(input()) 
    # int型のリスト
    A = list(map(int, input().rstrip().split(' ')))
    #print(A)
    
    # #TLE
    # ans = 0
    # for i, a in enumerate(A):
    #     target = A[i+a:]
    #     #print(target)
    #     for j, b in enumerate(target):
    #         if j  == b:
    #             #print(a, b)
    #             ans += 1
    # print(ans)
    
    L = [i+A[i] for i in range(N)]
    R = [i-A[i] for i in range(N)]
    c_l = collections.Counter(L)
    c_r = collections.Counter(R)
    #print(L)
    #print(c_l)
    #print(R)
    #print(c_r)
    ans = 0
    for k, v in c_l.items():
        v_ = c_r.get(k, 0)
        ans += v * v_
    print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int, input().split()))
D={}
E={}
for i in range(N):
  a=i+A[i]
  b=i-A[i]
  D.setdefault(a,0)
  E.setdefault(b,0)
  D[a]+=1
  E[b]+=1
ans=0
for i in D:
  if i in E:
    ans+=D[i]*E[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

ans = 0
for i in range(n):
    ans += ap[a[i] + i]
print(ans)

Submission status: Accepted

Solution code:
from _collections import defaultdict
import sys

read = sys.stdin.buffer.read
N = int(input())
A = [int(i) for i in input().split()]
D = defaultdict(int)

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

ans = 0
for i, a in enumerate(A, 1):
    ans += D[i + a]
print(ans)

Submission status: Accepted

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools, copy
from math import *
from bisect import *
from heapq import *
from collections import *


def lcm(a, b):  
    return (a*b)/gcd(a, b)

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N = In.int()
A = In.ints()
drueb = [defaultdict(int) for i in range(N)]

for i in range(N):
    # if i>=1:
    #     drueb[i] = copy.copy(drueb[i-1])
    val = i+1
    drueb[-1][A[i]-val] += 1

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

    if j<len(drueb):
        if -A[i]-(i+1) in drueb[-1]:
            ans+=drueb[-1][-A[i]-(i+1)]
    
Out.int(ans)
        
######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Accepted

Solution code:
n = int(input())
A=list(map(int,input().split()))
cnt=0
B=[]
C=[]
for i,a in enumerate(A):
    B.append(A[i]+i)
    C.append(A[i]-i)
from collections import Counter
Bd=dict(Counter(B))
Cd=dict(Counter(C))
cnt=0
for k in Bd.keys():
    b=Bd.get(k)
    c=Cd.get(-k)
    if b and c:
        cnt+=b*c
print(cnt)

Submission status: Accepted

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

d = [0]*N
ans = 0
for i in range(N):
    a = A[i]
    l,r = i+a, i-a
    if 0 <= l < N:
        d[l] += 1
    if 0 <= r < N:
        ans += d[r]

print(ans)

Submission status: Accepted

Solution code:
import sys
import array

if __name__ == "__main__":
    N = int(sys.stdin.readline().strip())
    A = array.array('i', [int(a) for a in sys.stdin.readline().strip().split(" ")])

    count_pair = 0
    L = {}
    R = {}

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

        if l in L:
            L[l].append(i+1)
        else:
            L[l] = [i+1]

        if r in R:
            R[r].append(i+1)
        else:
            R[r] = [i+1]

    print(sum([len(L[m]) * len(R[m]) for m in list(set(L.keys()) & set(R.keys()))]))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
n = int(sys.stdin.readline())
a = inpl()
dic ={}
res = 0
for i in range(n):
    res += dic.get(i - a[i], 0)
    dic[i + a[i]] = dic.get(i + a[i], 0) + 1

print(res)

Submission status: Accepted

Solution code:
n = int(input())
A=list(map(int,input().split()))
cnt=0
B=[]
C=[]
for i,a in enumerate(A):
    B.append(A[i]+i)
    C.append(A[i]-i)
from collections import Counter
Bd=dict(Counter(B))
Cd=dict(Counter(C))
cnt=0
for k in Bd.keys():
    try:
        cnt+=Bd[k]*Cd[-k]
    except KeyError:
        continue
print(cnt)