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:
def Binary_Search_Small_Count(A,x,equal=False,sort=False):
    """2分探索によって,x未満の要素の個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"未満"がx"以下"になる
    """
    if sort:
        A.sort()

    if A[0]>x or ((not equal) and A[0]==x):
        return 0

    L,R=0,len(A)
    while R-L>1:
        C=L+(R-L)//2
        if A[C]<x or (equal and A[C]==x):
            L=C
        else:
            R=C

    return L+1

def Binary_Search_Equal_Count(A,x,sort=False):
    """2分探索によって,xの個数を調べる.

    A:リスト
    x:調べる要素
    sort:ソートをする必要があるかどうか(Trueで必要)
    equal:Trueのときはx"を超える"がx"以上"になる
    """

    if sort:
        A.sort()

    if x<A[0] or A[-1]<x:
        return 0

    X=Binary_Search_Small_Count(A,x,equal=True)
    Y=Binary_Search_Small_Count(A,x,equal=False)
    return X-Y
#================================================
N=int(input())
A=["*"]+list(map(int,input().split()))

B=[0]*N
for j in range(1,N+1):
    B[j-1]=j-A[j]
B.sort()

K=0
del A[0]
for i in range(1,N+1):
    K+=Binary_Search_Equal_Count(B,i+A[i-1],False)
print(K)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
L = {}
R = {}
ans = 0
for i in range(N):
  t = i + 1 + A[i]
  if t in L:
    L[t] += 1
  else:
    L[t] = 1
  t = i + 1 - A[i]
  if t > 0:
    if t in R:
      R[t] += 1
    else:
      R[t] = 1
for i in R:
  if i in L:
    ans += R[i] * L[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import bisect

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

# ni - nj = ai + aj (i>j)
# ai - ni = - aj - nj

a1 = sorted([a[i] - (i+1) for i in range(n)])
a2 = sorted([- a[i] - (i+1) for i in range(n)])
ans = 0
for i in range(n):
    left = bisect.bisect_left(a2, a1[i])
    right = bisect.bisect_right(a2, a1[i])
    ans += (right - left)
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
A = [0] + A
Sam = []
Dif = []
D2= [0]*200000

for i in range(len(A)):
    Sam.append(i + A[i])
    if i - A[i] > 0:
        Dif.append(i - A[i])

for dif in Dif:
    D2[dif] += 1

count = 0
for sam in Sam:
    if sam < len(D2):
        count += D2[sam]

print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

'''
方針:
- 各A_i,(i<h)ごとにf(h,j)=A_h+A_j-|h-j|の値がf(i,j)に比べてどれだけ変化するかを計算し、
リストに格納(①)
- 各要素A_k,(j<k)ごとにf(i,k)=A_i+A_k-|i-k|の値がf(i,j)に比べてどれだけ変化するかを
計算し、カウントをとる(②)
- 再度ループを回して①と②を照合し、値が一致する組数をansに加算
'''

ans=0
diff_list=[] #①照合用の差分リスト
count=defaultdict(int) #②各要素がどれだけはみ出ているかのカウント
#前処理として、最初のループで①と②を作成
for i in range(1,N):
  if i == A[0]+A[i]:
    ans += 1
  d1 = A[i]-A[0]
  d2 = i
  diff_list.append(d1+d2)
  
  count[A[0]+A[i]-i] += 1

for i in range(N-1):
  count[A[0]+A[i+1]-(i+1)] -= 1 #その要素自身を忘れずに引く
  d = diff_list[i]
  ans += count[-d]
  
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
L = [0] * (404040)
A = map(int, input().split())
ans = 0
for i, a in enumerate(A):
    ia = i - a
    if ia >= 0:
        ans += L[ia]
    ai = a + i
    if ai < 404040:
        L[ai] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int, input().split()))
L = dict(Counter([i+A[i] for i in range(N)]))
R = dict(Counter([i-A[i] for i in range(N)]))
cnt = 0
for x in L:
    cnt += L[x]*R.get(x, 0)
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
b=dict(Counter([i-j for i,j in enumerate(a)]))
c=dict(Counter([i+j for i,j in enumerate(a)]))
cnt=0
for i in b:
  cnt+=b[i]*c.get(i,0)
print(cnt)

Submission status: Accepted

Solution code:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

#i - j == a[i] + a[j]
#=> i - a[i] == j + a[j]
#j - i == a[i] + a[j]
#=> i + a[i] == j - a[j]
n = INT()
a = LIST()
c = [0]*(2*n+1)
for i in range(n):
    if i - a[i] >= 0:
        c[i-a[i]] += 1
ans = 0
for i in range(n):
    if i + a[i] <= 2*n:
        ans += c[i+a[i]]
print(ans)

Submission status: Accepted

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

#i + Ai
plus = [0] * N
#i - Ai
minus = [0] * N

for i in range(N):
  plus[i] = i + 1 + A[i]
  minus[i] = i + 1 - A[i]
  
#print(plus, minus)  
plus = dict(collections.Counter(plus))
minus = dict(collections.Counter(minus))

#print(plus)
#print(minus)

ans = 0
for i in plus.keys():
  #print(i)
  if i in minus:
    #print(i)
    ans += plus[i] * minus[i]
    #print(ans)

print(ans)

Submission status: Accepted

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

    mp = dict()
    ans = 0
    for i in range(N):
        x = i - A[i]
        ans += mp.get(x, 0)
        y = A[i] + i
        mp[y] = mp.get(y, 0) + 1
    print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
n,*aa = map(int, open(0).read().split())
from collections import Counter
l_cnt = Counter()
r_cnt = Counter()

for i,a in enumerate(aa):
    l_cnt[i+a] += 1

for i,a in enumerate(aa):
    if i-a in l_cnt:
        r_cnt[i-a] += 1

ans = 0
for key in r_cnt:
    ans += l_cnt[key] * r_cnt[key]
print(ans)

Submission status: Accepted

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

B,C=[],[]
for i,j in enumerate(A):
    B.append(i+j+1)
    C.append((i+1)-j)

B,C=Counter(B),Counter(C)
ans=0
for i,j in B.items():
    ans +=j*C[i]
print(ans)

Submission status: Accepted

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

dic = {}

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

Submission status: Accepted

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

Submission status: Accepted

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

a_dict = dict()
b_dict = dict()

for i in range(n):
    a = h_list[i]+i
    b = i-h_list[i]
    if not a in a_dict:
        a_dict[a] = 1
    else:
        a_dict[a] += 1
    if not b in b_dict:
        b_dict[b] = 1
    else:
        b_dict[b] += 1

count = 0
for a in a_dict:
    if a in b_dict:
        count += a_dict[a]*b_dict[a]
print(count)

Submission status: Accepted

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

ipa = {}
ima = {}
for i in range(n):
    p = i + a[i]
    if p in ipa:
        ipa[p] += 1
    else:
        ipa[p] = 1
    m = i - a[i]
    if m in ima:
        ima[m] += 1
    else:
        ima[m] = 1

ans = 0
for k in ipa:
    if k in ima:
        ans += ipa[k] * ima[k]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
count = {}
for i in range(len(a)):#番号と身長を引く
    minus = (i+1) - a[i]
    if minus in count:
        count[minus] += 1
    else:
        count[minus] = 1
total = 0
for i in range(len(a)):
    plus = a[i] + (i+1)
    if plus in count:
        total += count[plus]
print(total)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[]
c=[]
ans=0
for i in range(n):
  b.append(i+1-a[i])
  c.append(a[i]+i+1)
x=max(b)
if x<=0:
  print(0)
  exit()
else:
  ans=0
  b_=[0]*(x+1)
  for i in range(n):
    if 0<=b[i]<=x:
      b_[b[i]]+=1
  for i in range(n):
    if 0<=c[i]<=x:
      ans+=b_[c[i]]
  print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

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

memo = defaultdict(int)  # 0で初期化する
answer = 0
for idx, x in enumerate(A, 1):  # indexを1から始める
    # i<jを満たしながらansを計算
    # idx = 1の時はansが増えることはない
    # idx = 2の時は、idx = 1の時の結果がmemoに記録されている
    # idx = 3の時は、idx=1,2の結果が記録されている
    # 以下同様
    answer += memo[idx - x]
    memo[idx + x] += 1

print(answer)

Submission status: Accepted

Solution code:
# 雰囲気で書いたら通ってしまったがなんで通ったかわからん
# i<jという前提を無視しているのではと感じる

N = int(input())
A = list(map(int, input().split()))
# i<jとして、条件は j-i = A_i + A_j
# i + A_i = j - A_j

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

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

# print(dict1, dict2)
ans = 0
for k, v in dict1.items():
    if k in dict2:
        ans += v * dict2[k]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
# i<jとして、条件は j-i = A_i + A_j
# i + A_i = j - A_j

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

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

# print(dict1, dict2)
ans = 0
for k, v in dict1.items():
    if k in dict2:
        ans += v * dict2[k]
print(ans)

Submission status: Accepted

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

    L={}
    R={}

    for i in range(N):
        l=(i+1)+A[i]
        r=(i+1)-A[i]
        if (l in L.keys()):
            L[l]+=1
        else:
            L[l]=1
        if r in R.keys():
            R[r]+=1
        else:
            R[r]=1

    res=0
    for key in L.keys():
        if key in R.keys():
            res+=R[key]*L[key]

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

Submission status: Accepted

Solution code:
import sys


def main():
    input = sys.stdin.buffer.readline
    n = int(input())
    a = list(map(int, input().split()))
    b = [0] * (10 ** 6)
    ans = 0
    for i in range(n):
        if i - a[i] > 0:
            ans += b[i - a[i]]
        if i + a[i] < 10 ** 6:
            b[i + a[i]] += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N = int(input())
L = list(map(int, input().split()))
import copy
U = copy.copy(L)
for i in range (0, N):
	L[i]+=(i+1)
	U[i]= -U[i]+(i+1)


L = sorted(L)
U = sorted(U)

import bisect

count = 0
for i in range (0, N):
	count+= bisect.bisect_right(U, L[i])-bisect.bisect_left(U, L[i])
    
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
b = defaultdict(int)
c = defaultdict(int)
n = int(input())
a = map(int, input().split())

for idx,i in enumerate(a, start=1):
  b[i - idx] += 1
  c[i + idx] += 1
ans = 0
for k,v in b.items():
  ans += (v * c[-1 * k])
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from collections import defaultdict
def main():
    n = int(input())
    a = list(map(int, input().split()))

    d1 = defaultdict(int)
    d2 = defaultdict(int)
    for i, ae in enumerate(a):
        d1[i + ae +1] += 1
        d2[i - ae +1] += 1
    r = 0
    for d1e in d1.keys():
        rt = d1[d1e] * d2[d1e]
        r += rt
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    from collections import defaultdict
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    d = defaultdict(int)
    ans = 0

    # KeyInsight:
    # j - i = Ai + Aj (j > i)、条件つきで絶対値の記号を外す
    # ▲: 計算量を落とす: 片方を固定して、考えられないか?
    # 左辺・右辺を独立として考えられないか?
    # See:
    # https://www.youtube.com/watch?v=OCRLlMa7kL0&feature=youtu.be
    for i in range(n):
        # jまでにiがどれだけ条件を満たすかを判定している
        # Ai + i = j - Aj
        # jの計算に相当
        diff = i - a[i]
        ans += d[diff]

        # iの計算に相当
        summed = i + a[i]
        d[summed] += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    from collections import defaultdict
    import sys
    input = sys.stdin.readline

    n = int(input())
    a = list(map(int, input().split()))
    d = defaultdict(int)
    ans = 0

    for i in range(n):
        diff = i - a[i]
        ans += d[diff]

        summed = i + a[i]
        d[summed] += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

s = [i+a for i, a in enumerate(A)]
t = [j-a for j, a in enumerate(A)]

d = Counter(s)
ans = 0

for i in t:
    ans += d[i]
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, 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:
import sys
from collections import defaultdict

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    L = defaultdict(int)
    R = defaultdict(int)
    for i in range(N):
        L[i+1+A[i]] += 1
        R[i+1-A[i]] += 1
    ans = 0
    for key, value in L.items():
        ans += value*R[key]
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,collections
input = sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))
B = []
C = []
for i,a in enumerate(A):
    B.append(i+a)
    C.append(i-a)
cnt = 0
Bc = collections.Counter(B)
Cc = collections.Counter(C)

for key,val in Bc.items():
    cnt += val*Cc[key]
print(cnt)

Submission status: Accepted

Solution code:

from collections import defaultdict

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

ctr = defaultdict(int)
ans = 0
for i in range(N):
    ctr[i + X[i]] += 1
    ans += ctr[i - X[i]]

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
#j-i = Ai+A　⇄　j-A[j] = A[i]+i
for i in range(n):
    Sum = A[i] + i
    dic[Sum] += 1
    Dif = i - A[i]
    ans += dic[Dif]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
b1,b2,dic,ans = [],[],{},0
for i, j in enumerate(a):
    b1.append(j-i)
    b2.append(-j-i)
for i, j in zip(b1, b2):
    if i in dic:
        ans += dic[i]
    if j in dic:
        dic[j] += 1
    else:
        dic[j] = 1
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)]

p = {}
m = {}
for i in range(N):
    if L[i] not in p:
        p[L[i]] = 1
    else:
        p[L[i]] += 1
for i in range(N):
    if R[i] not in m:
        m[R[i]] = 1
    else:
        m[R[i]] += 1

lower = max(min(p), min(m))
upper = min(max(p), max(m))
ans = 0
for x in range(lower, upper + 1):
    if x in p and x in m:
        ans += p[x] * m[x]

print(ans)

Submission status: Accepted

Solution code:
import collections

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

# ap+aq == p-q (p>q)
# p-ap = q+aq

mp = {}
ans = 0
for p in range(N):
    if p-A[p]+1 in mp:
        ans += mp[p-A[p]+1]
    if p+A[p]+1 in mp:
        mp[p+A[p]+1] += 1
    else:
        mp[p + A[p] + 1] = 1

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
p = {}
m = {}
for i in range(N):
    if p.get(i+A[i]) is None:
        p[i+A[i]] = 1
    else:
        p[i+A[i]] += 1
for i in range(N):
    if m.get(i-A[i]) is None:
        m[i-A[i]] = 1
    else:
        m[i-A[i]] += 1
for x in range(min(p),max(m)+1):
    if x in p and x in m:
        ans += p[x] * m[x]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter as C
n=int(input())
a=list(map(int,input().split()))
l=C([i+a[i]for i in range(n)])
r=C([i-a[i]for i in range(n)])
b=0
for i in l.keys():
    b+=l[i]*r[i]
print(b)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = [0]
A += list(map(int, input().split()))
cnt = 0
L = [- 10 ** 6]
R = [- 10 ** 6]

for i in range(1, N + 1):
    L.append(i + A[i])
    R.append(i - A[i])
c = collections.Counter(L)

for j in range(1, N + 1):
    cnt += c.get(R[j], 0)
print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin
import sys
import math
from functools import reduce
import functools
import itertools
from collections import deque,Counter
from operator import mul
import copy
# ! /usr/bin/env python
# -*- coding: utf-8 -*-
import heapq

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

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

pp = Counter(p)
qq = Counter(q)

ans = 0
for d in pp.items():
    ans += d[1] * qq[d[0]]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = list(map(int,input().split()))
addarr = [i+1+arr[i] for i in range(n)]
diffarr = [i+1-arr[i] for i in range(n)]

from collections import Counter
cnt = Counter([addarr[0]])
ans = 0

for i in range(1,n):
    tmp = diffarr[i]
    ans += cnt[tmp]
    cnt.update([addarr[i]])

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int, input().split()))
dAl = defaultdict(int)
dAr = defaultdict(int)
for i in range(N):
    L = (i + 1) + A[i]
    R = (i + 1) - A[i]
    dAl[L] += 1
    dAr[R] += 1

# dictの中を見る
ans = 0
for k, v in dAl.items():
    ans += v * dAr[k]
print(ans)

Submission status: Accepted

Solution code:
import itertools
from collections import deque,defaultdict,Counter
from itertools import accumulate
import bisect
from heapq import heappop,heappush,heapify
import math
from copy import deepcopy
import queue
#import numpy as np
# sympy as syp(素因数分解とか)
Mod = 1000000007
fact = [1, 1]
factinv = [1, 1]
inv = [0, 1] 
for i in range(2, 10**5 + 1):
    fact.append((fact[-1] * i) % Mod)
    inv.append((-inv[Mod % i] * (Mod // i)) % Mod)
    factinv.append((factinv[-1] * inv[-1]) % Mod)
    
def cmb(n, r, p):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n - r] % p
    
def sieve_of_eratosthenes(n):
    if not isinstance(n,int):
        raise TypeError("n is not int")
    if n<2:
        raise ValueError("n is not effective")
    prime = [1]*(n+1)
    for i in range(2,int(math.sqrt(n))+1):
        if prime[i] == 1:
            for j in range(2*i,n+1):
                if j%i == 0:
                    prime[j] = 0
    res = []
    for i in range(2,n+1):
        if prime[i] == 1:
            res.append(i)
    return res

 
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n+1)]
        self.rank = [0 for i in range(n+1)]
    
    def findroot(self,x):
        if x == self.parent[x]:
            return x
        else:
            y = self.parent[x]
            y = self.findroot(self.parent[x])
            return y
    
    def union(self,x,y):
        px = self.findroot(x)
        py = self.findroot(y)
        if px < py:
            self.parent[y] = px
        else:
            self.parent[px] = py
 
    def same_group_or_no(self,x,y):
        return self.findroot(x) == self.findroot(y)
def pow_k(x, n):

    if n == 0:
        return 1

    K = 1
    while n > 1:
        if n % 2 != 0:
            K *= x
        x *= x
        n //= 2

    return K * x
def main():  #startline-------------------------------------------
    n = int(input())
    a = list(map(int, input().split()))
    d = defaultdict(int)
    ans = 0
    for i in range(n):
        l = i - a[i]
        ans += d[l]
        d[a[i] + i] += 1
        
    print(ans)
if __name__ == "__main__":
    main() #endline===============================================

Submission status: Accepted

Solution code:
from collections import Counter

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

p = [i+Ai for i, Ai in zip(range(1, N+1), A)]
q = [j-Aj for j, Aj in zip(range(1, N+1), A)]

pc = Counter(p)
qc = Counter(q)

r = sum(pc[k]*qc[k] for k in pc.keys() & qc.keys())

print(r)

Submission status: Accepted

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

input = sys.stdin.readline

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

# 2人の持つ番号の差の絶対値が、2人の身長の和に等しい。
# j - i = Ai + Aj
# j - Aj = Ai + i
l = [j - aj for j, aj in enumerate(a, 1)]
r = [i + ai for i, ai in enumerate(a, 1)]
cnt = collections.Counter(r)
ans = 0
for i in l:
    ans += cnt[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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


xc = Counter()
yc = Counter()
for i, v in enumerate(a):
    xc[i + v] += 1
    yc[i - v] += 1
ans = 0
for v in xc:
    ans += xc[v] * yc[v]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

def main():
    n = int(input())
    a = list(map(int, input().split()))
    d = defaultdict(lambda : 0)
    ans = 0
    for i, ai in enumerate(a, 1):
        num = str(ai+i)
        d[num] += 1
        ans += d[str(i-ai)]
    print(ans)
        

if __name__ == "__main__":
    main()

Submission status: Accepted

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

x = [ aa + i  for i,aa in enumerate(a,start = 1)]
y = [ i - aa  for i,aa in enumerate(a,start = 1)]

from collections import Counter
c = Counter(y)
ans = 0
for xx in x:
    ans += c[xx]
print(ans)

Submission status: Accepted

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

for i in range(N):
    if i-A[i]+1 < 0:
        continue
    if i-A[i]+1 >= N:
        continue
    ans += start[i-A[i]+1]

print(ans)

Submission status: Accepted

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

l_count = defaultdict(int)
r_count = defaultdict(int)
for i, A in enumerate(As):
    l_count[i + A] += 1
    r_count[i - A] += 1
    
ans = 0
for k, lv in l_count.items():
    rv = r_count[k]
    ans += lv * rv

print(ans)

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right, bisect_left
sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    A_i, A_j = [], []
    for i in range(n):
        A_i.append(-A[i] - (i + 1))

    for j in range(n):
        A_j.append(A[j] - (j + 1))

    A_j.sort()

    res = 0
    for a in A_i:
        idx_1 = bisect_left(A_j, a)
        idx_2 = bisect_right(A_j, a)
        res += idx_2 - idx_1
    print(res)
    

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

ans = 0
for i, v in enumerate(a):
    ans += counter[i - v]
    counter[i + v] += 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 a, i in enumerate(A, 1)]
R = [a-i for a, i in enumerate(A, 1)]

ans = 0
R_c = Counter(R)
for l in L:
    ans += R_c[l]

print(ans)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = [0] + [int(i) for i in input().split()]

sum_list = [i + A[i] for i in range(1, N+1)]
sum_list.sort()

count = 0
for i in range(1, N+1):
  v = i - A[i]
  idx_right = bisect.bisect_right(sum_list, v)
  idx_left = bisect.bisect_left(sum_list, v)
  if idx_right > 0 and sum_list[idx_right-1] == v:
    count += idx_right - idx_left
print(count)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

d=defaultdict(int)
sm=0
for i in range(n):
  d[i+a[i]]+=1
  sm+=d[i-a[i]]
print(sm)

Submission status: Accepted

Solution code:
from collections import Counter

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

l1=[i+a[i] for i in range(n)]
l2=[i-a[i] for i in range(n)]

c2=Counter(l2)

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

l1=[i+a[i] for i in range(n)]
l2=[i-a[i] for i in range(n)]

c1=Counter(l1)
c2=Counter(l2)

ans=0
for i in c1:
  ans+=c1[i]*c2[i]

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
nii=lambda:map(int,stdin.readline().split())
lnii=lambda:list(map(int,stdin.readline().split()))
from collections import Counter

n=int(input())
a=lnii()

l1=[i+a[i] for i in range(n)]
l2=[i-a[i] for i in range(n)]

c1=Counter(l1)
c2=Counter(l2)

ans=0
for i in c1:
  ans+=c1[i]*c2[i]

print(ans)

Submission status: Accepted

Solution code:

from collections import defaultdict
from bisect import bisect_left

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

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

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

print(ans)

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter
n = int(input())
a = np.array(list(map(int, input().split())))
ni = np.array([i for i in range(n)])

ap = a + ni
an = (a - ni) * -1

cp = Counter(ap)
cn = Counter(an)

ans = 0
for i in cp.keys():
  ans += cp[i] * cn[i] 

print(ans)

Submission status: Accepted

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

ans = 0
dic1 = {}
dic2 = {}
for i in range(n):
    tmp1 = a[i] + (i + 1)
    tmp2 = -a[i] + (i + 1)
    if tmp1 in dic1:
        dic1[tmp1] += 1
    else:
        dic1[tmp1] = 1
    if tmp2 in dic2:
        dic2[tmp2] += 1
    else:
        dic2[tmp2] = 1
for key in dic1.keys():
    if key in dic2:
        ans += dic1[key] * dic2[key]
print(ans)

Submission status: Accepted

Solution code:
import sys 
from collections import Counter
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N = int(readline())
A = list(map(int,readline().split()))
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i] = (i+1) + A[i]
    Y[i] = (i+1) - A[i]  
cnt = Counter(Y)
ans = 0
for i in range(N):
    ans += cnt[X[i]] 
    cnt[Y[i]] -= 1
print(ans)

Submission status: Accepted

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

N = int(input().strip())
A_list = list(map(int, input().rstrip().split()))
#-----

plus_h = {}
minus_h = {}

for i in range(N):
    p = (i+1) + A_list[i]
    m = (i+1) - A_list[i]
    
    plus_h.setdefault(p, 0)
    plus_h[p] += 1
    
    minus_h.setdefault(m, 0)
    minus_h[m] += 1


cnt = 0

for k in plus_h:
    if k in minus_h:
        cnt += (plus_h[k] * minus_h[k])


print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
ma = max(A) + n -1 
P = [i+a+1 for i,a in enumerate(A) if i+a+1 <= ma]
Q = [j-a+1 for j,a in enumerate(A) if j-a+1 > 0]
 
cQ = Counter(Q)
cP = Counter(P)
ans = 0
for p in cP.keys():
    ans += cQ[p]*cP[p]
print(ans)