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:
import sys
sys.setrecursionlimit(1000000000)
import math
from math import gcd
def lcm(a, b): return a * b // gcd(a, b)
from itertools import count, permutations, chain
from functools import lru_cache
from collections import deque, defaultdict
from pprint import pprint
ii = lambda: int(input())
mis = lambda: map(int, input().split())
lmis = lambda: list(mis())
INF = float('inf')
N1097 = 10**9 + 7

def meg(f, ok, ng):
    while abs(ok-ng)>1:
        mid = (ok+ng)//2
        if f(mid):
            ok=mid
        else:
            ng=mid
    return ok

def get_inv(n, modp):
    return pow(n, modp-2, modp)

def factorials_list(n, modp):    # 10**6
    fs = [1]
    for i in range(1, n+1):
        fs.append(fs[-1] * i % modp)
    return fs

def invs_list(n, fs, modp):     # 10**6
    invs = [get_inv(fs[-1], modp)]
    for i in range(n, 1-1, -1):
        invs.append(invs[-1] * i % modp)
    invs.reverse()
    return invs

def comb(n, k, modp):
    num = 1
    for i in range(n, n-k, -1):
        num = num * i % modp
    den = 1
    for i in range(2, k+1):
        den = den * i % modp
    return num * get_inv(den, modp) % modp

def comb_from_list(n, k, modp, fs, invs):   
    return fs[n] * invs[n-k] * invs[k] % modp

#

class UnionFindEx:
    def __init__(self, size):
        #正なら根の番号、負ならグループサイズ
        self.roots = [-1] * size
    def getRootID(self, i):
        r = self.roots[i]
        if r < 0:   #負なら根
            return i
        else:
            r = self.getRootID(r)
            self.roots[i] = r
            return r
    def getGroupSize(self, i):
        return -self.roots[self.getRootID(i)]
    def connect(self, i, j):
        r1, r2 = self.getRootID(i), self.getRootID(j)
        if r1 == r2:
            return False
        if self.getGroupSize(r1) < self.getGroupSize(r2):
            r1, r2 = r2, r1
        self.roots[r1] += self.roots[r2]    #サイズ更新
        self.roots[r2] = r1
        return True

Yes = 'Yes'
No = 'No'


def main():
    N=ii()
    A=[None] + lmis()
    d = {}
    for i in range(1, N+1):
        A[i] -= i
        key = A[i]
        if key in d:
            d[key] += 1
        else:
            d[key] = 1
    ans = 0
    for i in range(1, N+1):
        b = -(A[i]+2*i)
        if b in d:
            ans += d[b]
    print(ans)




main()

Submission status: Accepted

Solution code:
n = int(input())
a_list = list(map(int,input().split()))
j_dict = {}
ans = 0
for i in range(n):
    if i+a_list[i]+1 not in j_dict.keys():
        j_dict[i+a_list[i]+1] = 0
    j_dict[i+a_list[i]+1] += 1
    if i-a_list[i]+1 in j_dict.keys():
        ans += j_dict[i-a_list[i]+1]


print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

n = int(input())
a = list(map(int, input().split()))
s = [n-1]

for i in range(1, n-1):
    s.append(s[0] - i - (a[i] - a[0]))

s.sort()
ans = 0
t = [a[0] + a[i] for i in range(1, n)]
for i, x in enumerate(t[::-1]):
    v = x + i
    ans += bisect_right(s, v) - bisect_left(s, v)

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict as d

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

som = []
diff = []

dsom = d(int)
ddiff = d(int)
for i in range(n):
	som.append(i+1+arr[i])
	diff.append((i+1-arr[i]))
	
	dsom[som[-1]] += 1
	ddiff[diff[-1]] += 1

val = 0
for k, v in dsom.items():
	val += (v * ddiff[k])
	
print(val)

Submission status: Accepted

Solution code:
# print('input >>')
N = int(input())
As = list(map(int,(input().split())))

tashi = {}
hiki = {}

for i in range(len(As)):
    sum_ = i + As[i]
    sub_ = i - As[i]
    if not sum_ in tashi:
        tashi[sum_] = 0
    if not sub_ in hiki:
        hiki[sub_] = 0
    tashi[sum_] += 1
    hiki[sub_] += 1

ans = 0

for k, v in tashi.items():
    if k in hiki:
        ans += v * hiki[k]

# print('-----output-----')
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
import collections
X = []
Y = []
for i in range(0,len(A)):
    X.append(i+1+A[i])
    Y.append(i+1-A[i])
x = collections.Counter(X)
n = 0
for j in range(0,len(Y)):
    n = n + x[Y[j]]
print(n)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
for i , j in enumerate(a):
    b[i]=j+i+1
c=[0]*n
q=[]
ans=0
for i , j in enumerate(a):
    c[i]=1+i-j
from collections import Counter
def combination(n, r):
    a = 1
    b = 1
    for i in range(r):
        a *= (n - i)
        b *= (i + 1)
    return a // b
cc=Counter(c)
bb=Counter(b)
f=bb&cc
for i in f.keys():
    ans+=bb[i]*cc[i]

print(ans)

Submission status: Accepted

Solution code:
import sys
import math
from collections import deque
import heapq
import itertools
import bisect
MAX_INT = int(10e10)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N = I()
a = IL()

for i in range(N):
  a[i] -= i
#print(a)

b = a[:]
b.sort()

#print(b)
ans = 0
for i in range(N):
  num = -((i+1) - 1)*2 - a[i]
  #print(i+1, num)
  #print(bisect.bisect_right(b, num))
  #print(bisect.bisect_left(b, num))
  #print("---")
  ans += bisect.bisect_right(b, num) - bisect.bisect_left(b, num)
print(ans)

Submission status: Accepted

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

import sys
import pprint

sys.setrecursionlimit(10 ** 6)

class Logger:
	def __init__(self, debug):
		self.debug = debug
	def print(self, *args):
		if self.debug:
			pprint.pprint(args)


def main():
	log = Logger(0)
	n = int(sys.stdin.readline())
	a = list(map(int, sys.stdin.readline().split()))
	# a_ext = {}
	b_sum_ext = {}
	b_ext = []
	# ai + aj = (j+1) - (i+1)
	# ai + i + 1 = -aj + j + 1

	for i, ai in enumerate(a):
		# a_ext[a[i] + i + 1] = 1
		log.print(a[i]+i+1, -a[i]+i+1)
		b_sum_ext[-a[i]+i+1] = b_sum_ext.get(-a[i]+i+1, 0)+1
	cnt = 0
	log.print(cnt)
	cnt = 0
	for i, ai in enumerate(a):
		b_sum_ext[-a[i]+i+1] = b_sum_ext.get(-a[i]+i+1, 0)-1
		if b_sum_ext.get(a[i] + i + 1, 0) != 0:
			log.print(i+1, a[i] + i + 1)
			cnt += b_sum_ext.get(a[i] + i + 1, 0)
	print(cnt)

	


main()

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0

diff = [i - A[i] for i in range(N)]
summ = [i + A[i] for i in range(N)]

cdiff = Counter(diff)

for i in range(N):
    if summ[i] in cdiff.keys():
        ans += cdiff[summ[i]]

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
from collections import Counter
input = stdin.readline

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

B = []


for i in range(N):
    B.append([A[i], i + 1])

# c...和, d..差
c = []
d = []

ans = 0

for i in range(N):
    if B[i][0] + B[i][1] == B[i][1] - B[i][0]:
        ans -= 1
    c.append(B[i][0] + B[i][1])
    d.append(B[i][1] - B[i][0])

c_count = Counter(c)
d_count = Counter(d)

c_lis = list(c_count.items())
d_lis = list(d_count.items())

c_lis.sort()
d_lis.sort()

n = 0

for c, num in c_lis:
    for i in range(n, len(d_lis)):
        if d_lis[i][0] < c:
            continue
        elif d_lis[i][0] == c:
            n = i + 1
            ans += num * d_lis[i][1]
        else:
            n = i
            break


print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
B = [i+1+A[i] for i in range(N)]
C = [i+1-A[i] for i in range(N)]
num = set(B) | set(C)


db = {n:0 for n in num}
dc = {n:0 for n in num}
for i in range(N):
  db[B[i]] += 1
  dc[C[i]] += 1

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

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_right, bisect_left

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


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


def main():
    N = int(input())
    A = list(map(int, input().split()))
    T = [i + 1 - A[i] for i in range(N)]
    idx = sorted(range(N), key=lambda k: T[k])
    T.sort()

    ans = 0
    for i in range(N):
        target = A[i] + i + 1
        left = bisect_left(T, target)
        if left > N - 1:
            continue
        if T[left] != target:
            continue
        else:
            right = bisect_right(T, target)
            ans += right - left
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import math
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int, input().split()))
    minus_A_plus_i = tuple([- A[i] + (i+1) for i in range(N)])
    A_plus_i = tuple([A[i] + (i+1) for i in range(N)])

    cnt = defaultdict(int)
    for e in minus_A_plus_i:
        cnt[e] += 1

    c = 0

    for item in A_plus_i:
        c += cnt[item]

    print(c)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

wa=[0]*n
sa=[0]*n
cntwa=[0]*(n+1)
cntsa=[0]*(n+1)
for i in range(n):
    wa[i]=i+1+a[i]
    sa[i] =i+1-a[i]
    if 0<wa[i]<n:
        cntwa[wa[i]]+=1
    if 0<sa[i]<n:
        cntsa[sa[i]]+=1
ans = 0
for i in range(n):
    ans += cntwa[i] * cntsa[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a_lst = [int(elem) for elem in input().split()]

dic = {}
for i in range(n):
    if not i - a_lst[i] in dic:
        dic[i - a_lst[i]] = 1
    else:
        dic[i - a_lst[i]] += 1
        
cnt = 0
for j in range(n):
    if j + a_lst[j] in dic:
        cnt += dic[j + a_lst[j]]

print(cnt)

Submission status: Accepted

Solution code:
import numpy as np
n = int(input())
a = np.array(list(map(int,input().split())))
b = np.array(a)
a += np.arange(n)+1
b -= np.arange(n)+1
b *= -1
a = np.sort(a)
b = np.sort(b)
c = 0
for i in a:
    l = np.searchsorted(b,i,side="left")
    r = np.searchsorted(b,i,side="right")
    c += r-l

print(c)

Submission status: Accepted

Solution code:
N=int(input())
A=list(map(int,input().split()))
B=[0]*N
C=[0]*N
for i in range(N):
  B[i]=A[i]+i+1
  C[i]=i+1-A[i]
B.sort()
C.sort()
start=0
j=0
bcount=1
bs=0
ans=0
for i in range(N-1):
  ccount=0
  x=B[i]
  
  if(x!=B[i+1]):
    bcount=i+1-bs
    #print(bcount)
    bs=i+1
    while(C[j]<=x):
      if(C[j]==x):
        ccount+=1
      if(j==N-1):
        break
      if(j<N-1):
        j+=1
      
    ans+=ccount*bcount
    #print(ccount)
#print(B)
#print(C)
print(ans)

Submission status: Accepted

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

from collections import Counter

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

num = list(range(1, N+1))

l1 = [] * N
l2 = [] * N

for i in range(N):
    l1.append(a[i] - num[i])
    l2.append(-a[i] - num[i])

k = list(set(l1) & set(l2))
c1 = Counter(l1)
c2 = Counter(l2)

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

print(ans)

Submission status: Accepted

Solution code:
from sys import stdin
import sys

N = int(input())
A = list(map(int, input().split()))
B = {}
C = {}
# B1=[]
# C1=[]
for i in range(len(A)):
    B[i+1-A[i]] = B.get(i+1-A[i], 0)+1
    C[i+1+A[i]] = C.get(i+1+A[i], 0)+1
    # B1.append(i+1-A[i])
    # C1.append(i+1+A[i])
# print(B)
# print(C)
# print(B1)
# print(C1)
cnt1 = 0
for i, v in enumerate(B):
    # print(i, v)
    if v in C.keys():
        # print(v)
        cnt1 += B.get(v)*C.get(v)

# cnt = 0
# for i in range(1, N+1):
#     for k in range(i+1, N+1):
#         if i != k and A[i-1] < N and A[k-1] < N:
#             if abs(i-k) == A[i-1]+A[k-1]:
#                 cnt += 1
print(cnt1)

Submission status: Accepted

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

tmp = [0] * n
tmp2 = [0] * n
for i, j in enumerate(a):
    if i + j < n:
        tmp[i + j] += 1
    if 0 <= i - j:
        tmp2[i - j] += 1

cnt = 0
for i in range(n):
    cnt += tmp[i] * tmp2[i]
print(cnt)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
inf = float('inf')
ninf = -float('inf')
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n=ii()
arr=limii()
ans=0
chk={}
for p in range(n):
    i=p+1

    if i-arr[p] in chk:
        ans+=chk[i-arr[p]]
        #print(p,i,arr[p],i-arr[p],chk)
    
    if i+arr[p] in chk:
        chk[i+arr[p]]+=1
    else:
        chk[i+arr[p]]=1
    #print(i+arr[p])
#print(list(chk.values()),ans)
print(ans)

Submission status: Accepted

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

def solve(N, A):
    from collections import defaultdict
    B = defaultdict(int)
    ans = 0
    for i, a in enumerate(A, 1):
        ans += B[a-i]
        B[-a-i] += 1
    return ans

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
def main():
    N = int(input())
    A = list(map(int, input().split()))
    print(solve(N, A))

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

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

migi = [0 for i in range(n)]
hidari = [0 for i in range(n)]
for i in range(n):
    idx = i+a[i]
    if idx < n:
        migi[idx] += 1
    idx = i-a[i]
    if idx >= 0:
        hidari[idx] += 1
ans = 0
for i in range(n):
    ans += migi[i] * hidari[i]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int, input().split()))
b=[0]*n
c=[0]*n
for i in range(n):
    b[i]=a[i]+i
    c[i]=i-a[i]
bs=sorted(b)
cs=sorted(c)
lx=[1+10**10]*n
ly=[2+10**10]*n
rx=[3+10**10]*n
ry=[4+10**10]*n

lx[0]=1
ly[0]=bs[0]
rx[0]=1
ry[0]=cs[0]

d=0
e=0
for j in range (1,n):
    if bs[j]==bs[j-1]:
        lx[d]+=1
    else:
        d+=1
        lx[d]=1
        ly[d]=bs[j]
        
for k in range (1,n):
    if cs[k]==cs[k-1]:
        rx[e]+=1
    else:
        e+=1
        rx[e]=1
        ry[e]=cs[k]
x=0
ans=0
for l in range(d):
    while ry[x]<=ly[l] and x<n-1:
        if ry[x]==ly[l]:
            ans+=(lx[l]*rx[x])
            x+=1
        else:
            x+=1
print(ans)

Submission status: Accepted

Solution code:
import bisect

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

mem =[0 for i in range(0,N +1,1)]
count =0

for i in range(N-1,-1,-1):
    if A[i]+i < N:
        count+=mem[A[i]+i]

    if i - A[i] > 0:
        mem[i - A[i]]+=1

print(count)

Submission status: Accepted

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

d1={}
for i,e in enumerate(As):
    d=i-e
    if d > 0:
        if d in d1.keys():
            d1[d]+=1
        else:
            d1[d]=1
cnt=0
for i,e in enumerate(As):
    if (i+e) in d1.keys():
        cnt += d1[i+e]
print(cnt)

Submission status: Accepted

Solution code:
from sys import stdin
def main():
    #入力
    readline=stdin.readline
    N=int(readline())
    A=list(map(int,readline().split()))
    B=[0]*N
    C=[0]*N
    for i in range(N):
        B[i]=A[i]-(i+1)
        C[i]=A[i]+(i+1)

    d=dict()
    for i in range(N):
        if B[i] not in d:
            d[B[i]]=1
        else:
            d[B[i]]+=1
    
    res=0
    for i in range(N):
        n=-1*C[i]
        if n not in d:
            pass
        elif n in d and d[n]>=1:
            res+=d[n]
            d[B[i]]-=1

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

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
T = []
K = []
for i in range(N):
    a = i - A[i] + 1
    if a >= 1:
        T.append(a)
hiku = Counter(T)

ans = 0
for j in range(N):
    a = j - A[j] + 1
    b = j + A[j] + 1
    ans += hiku[b]
    hiku[a] -= 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
# import sys

# input = sys.stdin.readline

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

A1 = [0]*N
A2 = [0]*N

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

c = Counter(A2)

cnt = 0
for i in range(N):
    cnt += c[A1[i]]

print(cnt)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
a_index = []
for i in range(n):
    a_index.append((i, a[i]))
dic1 = {}
dic2 = {}
for i in range(n):
    one = a_index[i][0] + a_index[i][1]
    two = a_index[i][0] - a_index[i][1]
    if one not in dic1:
        dic1[one] = 1
    else:
        dic1[one] += 1
    if two not in dic2:
        dic2[two] = 1
    else:
        dic2[two] += 1
ans = 0
for i in dic1.keys():
    if i in dic2:
        ans += dic2[i] * dic1[i]
for i in dic2.keys():
    if i in dic1:
        ans += dic1[i] * dic2[i]
        #print(i)
print(ans // 2)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
l=[int(x) for x in input().split()]
f1={}
f2={}
for i in range(1,len(l)+1):
	if i-l[i-1] in f1:
		f1[i-l[i-1]]+=1
	else:
		f1[i-l[i-1]]=1
	if l[i-1]+i in f2:
		f2[l[i-1]+i]+=1
	else:
		f2[l[i-1]+i]=1

c=0
#print(f1)
#print(f2)
for u,v in f1.items():
	c+=f2.get(u,0)*v
print(c)

Submission status: Accepted

Solution code:
def e_this_message_will_self_destruct_in_5s():
    from bisect import bisect_left
    N = int(input())
    A = [int(i) for i in input().split()]

    add = [j + a for j, a in enumerate(A, 1)]
    diff = sorted([k - a for k, a in enumerate(A, 1)])
    ans = 0
    for p in add:
        ans += bisect_left(diff, p + 1) - bisect_left(diff, p)
    return ans

print(e_this_message_will_self_destruct_in_5s())

Submission status: Accepted

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

li = [0]*(10**6+1)

for i in range(1,n):
    if ai[i] >= 2*10**5:
        continue
    li[ai[i]-i+5*10**5] += 1

ans = 0

for i in range(1,n):
    if ai[i-1] >= 2*10**5:
        continue
    #print(i)
    ans += li[-ai[i-1]-(i-1)+5*10**5]
    if i == n:
        #print(i,i,i)
        break
    if ai[i] < 2*10**5:
        li[ai[i]-i+5*10**5] -= 1
        
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    from collections import Counter
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline
    N = int(input())
    A = [int(x) for x in input().strip().split()]
    j_Aj = Counter([j-Aj for j, Aj in enumerate(A, start=1)])
    ans = 0
    for i, a in enumerate(A[:-1], start=1):
        if a > N:
            continue
        ans += j_Aj[a+i]

    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7
sys.setrecursionlimit(mod) # 再帰回数上限はでdefault1000

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

N = int(input())

A = LI()

A_ii = copy.deepcopy(A)
for i in range(N):
    A_ii[i] += i
dic_A_ii = collections.Counter(A_ii)

A_jj = copy.deepcopy(A)

for j in range(N):
    A_jj[j] = -1 * A_jj[j] + j

ans = 0
dic_A_jj = collections.Counter(A_jj)
# print(dic_A_ii)
# print(dic_A_jj)

for ii_key in dic_A_ii.keys():
    ans += dic_A_jj[ii_key] * dic_A_ii[ii_key]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
q = 0
z = 1000
p = []*z
m = []*z
for i in range(z):
    p.append([])
    m.append([])
for i in range(n):
    x = i+1-a[i]
    if(x > 0):
        if(x in p[x%z]):
            m[x%z][p[x%z].index(x)][0] += 1
        else:
            m[x%z].append([1,0])
            p[x%z].append(x)
    x = i+1+a[i]
    if(x in p[x%z]):
        m[x%z][p[x%z].index(x)][1] += 1
    else:
        m[x%z].append([0,1])
        p[x%z].append(x)
    
for i in range(z):
    for j in range(len(m[i])):
        q += m[i][j][0]*m[i][j][1]
print(q)

Submission status: Accepted

Solution code:
import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
l1 = [i+1+a[i] for i in range(n)]
l2 = [i+1-a[i] for i in range(n)]
c1 = Counter(l1)
c2 = Counter(l2)
res = 0
inter = set(l1) & set(l2)
for value in inter:
    res += c1[value]*c2[value]

print(res)

Submission status: Accepted

Solution code:
from collections import Counter

N = int(input())
A = list(map(int, input().split()))
X = []
Y = Counter()
for i in range(1, N+1):
    X.append(i-A[i-1])
    Y[A[i-1]+i] += 1
ans = 0
for x in X:
    if x < 2:
        continue
    ans += Y[x]
print(ans)

Submission status: Accepted

Solution code:
import collections

N = int(input())
A = list(map(int, input().split()))
ans = 0
p_list = []
m_list = []
for i in range(N):
    p_list.append(i + A[i])
    m_list.append(i - A[i])
p_c = collections.Counter(p_list)
m_c = collections.Counter(m_list)

for i in range(N):
    ans += p_c[i - A[i]]
    ans += m_c[i + A[i]]
print(ans//2)

Submission status: Accepted

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

P = {}
Q = {}

for i in range(N):
    if i+1 - A[i] in P:
        P[i+1 - A[i]] += 1
    else:
        P[i+1 - A[i]] = 1
    if i+1 + A[i] in Q:
        Q[i+1 + A[i]] += 1
    else:
        Q[i+1 + A[i]] = 1

res = 0
for k,v in P.items():
    if k in Q:
        res += v * Q[k]

print(res)

Submission status: Accepted

Solution code:
from collections import defaultdict
n = int(input())
al = list(map(int, input().split()))
ia = [(i+1) - a for i, a in enumerate(al)]
jb = [(i+1) + a for i, a in enumerate(al)]
# print(ia)
# print(jb)
d_ia = defaultdict(lambda: 0)
d_jb = defaultdict(lambda: 0)
for t in ia:
    d_ia[t] += 1
for t in jb:
    d_jb[t] += 1

ans = 0

for k, v in d_ia.items():
    ans += (d_jb[k]*v)
print(ans)

Submission status: Accepted

Solution code:
# python3

#===============================================================================
from collections import defaultdict, Counter
from functools import lru_cache
from heapq import heappush, heappop
from math import gcd, floor, ceil
from sys import stdin, stdout

def ilist():
    return [int(x) for x in stdin.readline().strip().split(" ")]
def iint():
    return int(stdin.readline().strip())
def istr():
    return stdin.readline().strip()
#===============================================================================


def solve(A):
    N = len(A)
    res = 0
    X = [A[i] + i for i in range(N)]
    Y = [A[i] - i for i in range(N)]
    #print(X, Y)
    d1 = Counter(X)
    d2 = Counter(Y)
    #print(d1, d2)
    for k in d1:
        res += d1[k] * d2[-k]
    return res


if __name__ == '__main__':
    N = iint()
    A = ilist()
    print(solve(A))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

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

li = []
for i in range(N):
    li.append(A[i] + i)

li.sort()

cnt = 0
for j in range(N):
    target = j - A[j]
    cnt += bisect_right(li, target) - bisect_left(li, target)

print(cnt)

Submission status: Accepted

Solution code:
from collections import deque, Counter

N = int(input())

A = [
  int(j) - i  for i, j in enumerate(input().split())
]
cnt_A = Counter(A)

ans = 0
d = deque(A)
for i in range(N):
  a = d.popleft()
  #c = d.count(-a - 2 * i)
  c = cnt_A[-a - 2 * i]
  ans += c
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
def dp3(ini, i, j, k): return [[[ini]*i for i2 in range(j)] for i3 in range(k)]
import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
A = li()

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

cnt = 0
for i in range(N):
    num = -2*(i+1)-A_r[i]
    ind_l = bisect.bisect_left(B, num)
    if B[ind_l] != num:
        continue
    ind_r = bisect.bisect_right(B, num)
    cnt += ind_r - ind_l

print(cnt)

Submission status: Accepted

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

mp = {}
for i, ai in enumerate(a):
    df = ai - (i + 1)
    if df in mp:
        mp[df] += 1
    else:
        mp.update({df: 1})
ans = 0
for i, ai in enumerate(a):
    s = -(ai + i + 1)
    if s in mp:
        ans += mp[s]

print(ans)

Submission status: Accepted

Solution code:
n = int(input())
arr = [int(s) for s in input().split()]
freq = {}
count=0
for i in range(len(arr)):
    if i-arr[i] in freq:
        count+=freq[i-arr[i]]
    if arr[i]+i in freq:
        freq[arr[i]+i] = freq[arr[i]+i] + 1
    else:
        freq[arr[i]+i] = 1
print(count)

Submission status: Accepted

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

S = {}
cnt=0
for i in range(N):
    if i-A[i] in S:
        cnt+=S[i-A[i]]
    t = A[i]+i
    if t in S:
        S[t]+=1
    else:
        S[t]=1

print(cnt)

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = list(map(int,input().split()))
B = []
C = []
for i in range(N):
    B.append(-A[i]+i+1)
    C.append(A[i]+i+1)

bol = collections.Counter(B)
col = collections.Counter(C)

#print(col)
count = 0
for i,j in list(bol.items()):
    if col[i]:
        count += j*col[i]

print(count)

Submission status: Accepted

Solution code:
import numpy as np
from collections import Counter

N = int(input())
A = np.array(list(map(int, input().split())))
B = np.arange(N) + 1

s = A + B
m = B - A

s_ct = Counter(s)
m_ct = Counter(m)

ans = 0
for i in s_ct:
    ans += s_ct[i] * m_ct[i]

print(ans)