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:
n = int(input())
a = list(map(int,input().split()))
b = [0]*n
c = [0]*n
for i in range(n):
    b[i] = i - a[i]
for j in range(n):
    c[j] = a[j] + j
b.sort()
c.sort()
#print(b)
#print(c)
i = 0
j = 0
k = 0
m = 0
count = 0
while i < n and j < n:
    if b[i] < c[j]:
        i += 1
    elif b[i] > c[j]:
        j += 1
    else:
        k = i
        m = j
        ck = 0
        cm = 0
        while k < n - 1:
            if b[k] == b[k+1]:
                ck += 1
                k += 1
            else:
                break
        while m < n - 1:
            if c[m] == c[m+1]:
                cm += 1
                m += 1
            else:
                break
        if ck == 0 and cm == 0:
            count += 1
            if i < n-1:
                i += 1
            elif j < n-1:
                j += 1
            else:
                i += 1
                j += 1
        elif ck == 0:
            count += cm + 1
            j = m + 1
        elif cm == 0:
            count += ck + 1
            i = k + 1
        else:
            count += (ck+1)*(cm+1)
            i = k + 1
            j = m + 1        
print(count)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())

a = list(map(int, input().split()))
b = []
c = []

for i in range(n):
	b.append(-(i + 1 + a[i]))
	c.append(a[i] - i - 1)

#print(a)
#print(b)
#print(c)

counts = {}

result = 0

counts[b[0]] = 1

for i in range(1, n):
	x = c[i]

#	print(x)
	#print(counts)

	if x in counts: 
		result += counts[x]

	y = b[i]
	if y in counts:
		counts[y] += 1
	else: 
		counts[y] = 1


	


print(result)

Submission status: Accepted

Solution code:
def m():
    N = int(input())
    A = [0] + list(map(int, input().split()))
    length = len(A)
    x = [i - A[i] for i in range(length)]
    y = [i + A[i] for i in range(length)]
    xdict = {}
    ydict = {}
    for i in range(1, length):
        xdict[x[i]] = xdict[x[i]] + 1 if xdict.get(x[i], 0) else 1
        ydict[y[i]] = ydict[y[i]] + 1 if ydict.get(y[i], 0) else 1

    ans = 0
    for k, v in xdict.items():
        ans = ans + ydict[k] * v if ydict.get(k, 0) else ans
    return ans


print(m())

Submission status: Accepted

Solution code:
from sys import stdin
from collections import Counter
N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()]
 
d1 = []
d2 = []
 
for ind,i in enumerate(A):
    d1.append(ind+i)
    d2.append(ind-i)
    
c1 = Counter(d1)
c2 = Counter(d2)

ans = 0
for i in c1.keys():
    ans += (c1[i]*c2[i])
 
print(ans)

Submission status: Accepted

Solution code:
def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    d1 = {}
    d2 = {}
    for i in range(n):
        if i + a[i] not in d1:
            d1[i + a[i]] = 1
        else:
            d1[i + a[i]] += 1
    s1 = set(d1.keys())
    for i in range(n):
        if i - a[i] not in d2:
            d2[i - a[i]] = 1
        else:
            d2[i - a[i]] += 1
    s2 = set(d2.keys())
    s = list(s1 & s2)
    c = 0
    for i in s:
        c += d1[i] * d2[i]
    print(c)

main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
box = [[0,0] for i in range(n)]

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

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
b=[0]*n
c=[0]*n
d=0
sums=0
for j in range(n):
    if j-a[j]<1:
        das=0
    else:
        b[j-a[j]]=b[j-a[j]]+1
    if j+a[j]>n-2:
        das=0
    else:
        c[j+a[j]]=c[j+a[j]]+1
for k in range(n):
    d=b[k]*c[k]
    sums=sums+d
print(sums)

Submission status: Accepted

Solution code:
import bisect

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n = int(input())
a_array = map(int, input().split())
point_array = [[0, 0] for _ in range(n)]
for i, a in enumerate(a_array):
    if 0 <= i - a < n:
        point_array[i - a][1] += 1
    if 0 <= i + a < n:
        point_array[i + a][0] += 1
ans = 0
for bp, ap in point_array:
    ans += bp * ap
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()
A = LIST()

A = [x-i for i, x in enumerate(A)]
cnt_A = Counter(A)

ans = 0
for i, a in enumerate(A):
    ans += cnt_A[-A[i]-2*i]
print(ans)

Submission status: Accepted

Solution code:
n = int(input())
H = list(map(int, input().split()))
H2 = [0]*n
H3 = [0]*n

for i in range(n):
  H2[i] = H[i] - i 
  H3[i] = - (H[i] + i)
#Hb - iB = - (iA + Ha)
#-(Ha - iA) = Hb + iB

import collections 
c2 = collections.Counter(H2)
c3 = collections.Counter(H3)

ans = 0
for k2 in c2:
  if k2 in c3:
    ans += c3[k2] * c2[k2]
print(ans)  
#iB - iA = Ha + Hb
#iA - iB = Ha + Hb
#Hb - iB = - (iA + Ha)
#-(Ha - iA) = Hb + iB

Submission status: Accepted

Solution code:
n = int(input())
As = list(map(int,input().split()))
kplsAk = [As[i]+i+1 for i in range(n)]
dic ={}
ans = 0

for i in range(n):
    key1 = i+1-As[i]
    key2 = As[i]+i+1
    if key1 in dic:
        ans +=dic[key1]
    if  key2 not in dic:
        dic[key2] = 1
    else:
        dic[key2] += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())

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

num = []

for i in range(n):
    num.append((i+1)-a[i])

ct = Counter(num)

ans = 0
for i in range(n):
    scan = (i+1) + a[i]
    if(ct[scan] != 0):
        ans += ct[scan]

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
wa={}
sa={}
for i in range(n):
    wa_=a[i]+(i+1)
    sa_=(i+1)-a[i]
    if 0<sa_:
        if sa_ in sa:
            sa[sa_]+=1
        else:
            sa[sa_]=1
    if wa_ in wa:
        wa[wa_]+=1
    else:
        wa[wa_]=1
ans=0
for i in range(n):
    wa_=a[i]+(i+1)
    sa_=(i+1)-a[i]
    if wa_ in sa:
        ans+=sa[wa_]
    if sa_ in wa:
        ans+=wa[sa_]
print(ans//2)
#print(wa)
#print(sa)

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)

Submission status: Accepted

Solution code:
import math
import sys
def input():
    return sys.stdin.readline().rstrip('\n')


def calc(N, A):
    result = 0
    diff = [i - A[i] for i in range(N)]
    d1 = {}
    for x in diff:
        d1[x] = (d1[x] if x in d1 else 0) + 1 
    plus = [i + A[i] for i in range(N)]
    d2 = {}
    for x in plus:
        d2[x] = (d2[x] if x in d2 else 0) + 1
    for x in d1:
        y = d2[x] if x in d2 else 0
        result += d1[x] * y
    return result
    

N = int(input())
A = [int(s) for s in input().split()]
print(calc(N, A))

Submission status: Accepted

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

Submission status: Accepted

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

i_plus_Ai = [0 for i in range(N)]
dict = {}
for i in range(N):
    i_plus_Ai[i] = i + As[i]
    tmp = i - As[i]
    if tmp not in dict:
        dict[tmp] = [i]
    else:
        dict[tmp].append(i)

count = 0
for i in range(N):
    if i_plus_Ai[i] in dict:
        kouho = dict[i_plus_Ai[i]]
        for j in range(len(kouho)):
            if kouho[j] > i:
                count += len(kouho) - j
                break

print(count)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A_list = [int(x) for x in input().split()]
plus_list = [int(x) - (i+1) for i, x in enumerate(A_list)]
minus_list = [int(x) + (i + 1) for i, x in enumerate(A_list)]
# print(plus_list)
# print(minus_list)
dic = {}
for i, p in enumerate(plus_list):
    j = i+1
    if p in dic.keys():
        dic[p].append(j)
    else:
        dic[p] = [j]  # already sorted

ans = 0
for i, m in enumerate(minus_list[:-1]):
    j = i + 1
    if - 1 * m not in dic.keys():
        continue
    candidates = dic[-1 * m]
    # print(candidates, j)
    # print(bisect.bisect_left(candidates, j))
    ans += len(candidates) - bisect.bisect_left(candidates, j)
print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left,bisect_right

N=int(input())
A=list(map(int,input().split()))
C=[0]*N
for i in range(N):
  C[i]=[i+1,A[i],i+1-A[i],A[i]-(i+1),A[i]+(i+1)]
  
#ID/身長/ID-身長/身長-ID/合計
C.sort(key=lambda x:x[4])
D=[C[i][4] for i in range(N)]

#print(C)
cnt=0
for num in C:
  s=bisect_left(D,num[2])
  t=bisect_right(D,num[2])
  #print(num,s,t)
  cnt += t-s
print(cnt)

Submission status: Accepted

Solution code:
# coding: utf-8

import bisect


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

    j_minus_aj_ = sorted([(j - A[j], j) for j in range(N)])
    j_minus_aj, j_minus_aj_j = [None] * N, [None] * N
    for j in range(N):
        j_minus_aj[j], j_minus_aj_j[j] = j_minus_aj_[j]

    j_plus_aj_ = sorted([(j + A[j], j) for j in range(N)])
    j_plus_aj, j_plus_aj_j = [None] * N, [None] * N
    for j in range(N):
        j_plus_aj[j], j_plus_aj_j[j] = j_plus_aj_[j]

    ans = 0

    for i in range(N):
        # i <= j
        i_plus_ai = i + A[i]

        left = bisect.bisect_left(j_minus_aj, i_plus_ai)
        right = bisect.bisect_right(j_minus_aj, i_plus_ai)

        # for j in range(left, right):
        #     if j_minus_aj_j[j] >= i:
        #         ans += 1
        ans += right - left
        
        i_minus_ai = i - A[i]

        left = bisect.bisect_left(j_plus_aj, i_minus_ai)
        right = bisect.bisect_right(j_plus_aj, i_minus_ai)

        # for j in range(left, right):
        #     if j_plus_aj_j[j] < i:
        #         ans += 1
        ans += right - left
    
    return ans // 2

    # for i in range(N):
    #     # i <= j
    #     i_plus_ai = i + A[i]
    #     # left = geq_search(j_minus_aj, i_plus_ai-1)
    #     # dif = 0
    #     # while left+dif+1 < N and j_minus_aj[left+dif+1] != i_plus_ai:
    #     #     dif += 1
    #     # left = left + dif
    #     left = bisect.bisect_left(j_minus_aj, i_plus_ai)

    #     # right = leq_search(j_minus_aj, i_plus_ai+1)
    #     # dif = 0
    #     # while 0 <= right-dif-1 and j_minus_aj[right-dif-1] != i_plus_ai:
    #     #     dif += 1
    #     # right = right - dif
    #     right = bisect.bisect_left(j_minus_aj, i_plus_ai)

    #     for j in range(left, right):
    #         if j_minus_aj_j[j] >= i:
    #             ans += 1
        
    #     i_minus_ai = i - A[i]
    #     # left = geq_search(j_plus_aj, i_minus_ai-1)
    #     # dif = 0
    #     # while left+dif+1 < N and j_plus_aj[left+dif+1] != i_minus_ai:
    #     #     dif += 1
    #     # left = left + dif
    #     left = bisect.bisect_left(j_plus_aj, i_minus_ai)

    #     # right = leq_search(j_plus_aj, i_minus_ai+1)
    #     # dif = 0
    #     # while 0 <= right-dif-1 and j_plus_aj[right-dif-1] != i_minus_ai:
    #     #     dif += 1
    #     # right = right - dif
    #     right = bisect.bisect_left(j_plus_aj, i_minus_ai)

    #     for j in range(left, right):
    #         if j_plus_aj_j[j] < i:
    #             ans += 1
    
    # return ans


print(main())

Submission status: Accepted

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
dp = [0] * 10 ** 7
ans = 0
for i in range(N):
    x = i + 1 - A[i]
    if x >= 0:
        ans += dp[x]
    y = i + 1 + A[i]
    if y < 10 ** 7:
        dp[y] += 1

print(ans)

Submission status: Accepted

Solution code:
import collections


def main():
    n = int(input())
    a = list(map(int,input().split()))
    ans = 0
    c = [-a[i]-i for i in range(n)]
    # print(c)
    c = collections.Counter(c)
    for i in range(n):
        ans += c[a[i]-i]

    #
    # print(c)
    # c = collections.Counter(a[0])
    # for i in range(n-1):
    #     for j in range(i,n):
    #         if j-i == a[i]+a[j]:
    #             # print(i+1,j+1)
    #             ans += 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import (
    bisect_left,
    bisect_right,
)

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

pl = [i + v for i, v in enumerate(a)]

spl = sorted(pl)

c = 0

for j, v in enumerate(a):
    w = j - v
    left = bisect_left(spl, w)
    right = bisect_right(spl, w)
    tmp = right - left
    c += tmp

print(c)

Submission status: Accepted

Solution code:
from collections import Counter
ans = 0
N = int(input())
Alist = list(map(int, input().split()))
A0 = Alist[0]
add = A0
res_ = []
for i in range(N):
    res_.append(Alist[i]+A0-i)
res = Counter(res_)
ans += res[0]
sbn = 0
for i in range(1, N):
    res[res_[i-1]] -= 1
    sbn += Alist[i] - Alist[i-1] + 1
    ans += res[-sbn]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
ans = 0
dic = {}
for i in range(1,N):
  x = i-A[i]
  if x<0:
    continue
  else:
    if x in dic:
      dic[x]+=1
    else:
      dic[x]=1
if A[0] in dic:
  ans+=dic[A[0]]
for i in range(1,N):
  x = i+A[i]
  
  if i-A[i] in dic:
    dic[i-A[i]]-=1
    
  if x in dic:
    ans+=dic[x]
  
print(ans)

Submission status: Accepted

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

fromLeft = [-1]*n

for i in range(n):
    fromLeft[i] = a[i] - i

ans = 0

ldList = [0]*(n*2+5)

for i in reversed(range(n)):
    if 0 <= fromLeft[i]+n+1 and fromLeft[i]+n+1 < n*2+5:
        ldList[fromLeft[i]+n+1] += 1
    if 0 <= -1*a[i]-i+n+1 and -1*a[i]-i+n+1 < n*2+5:
        ans += ldList[-1*a[i]-i+n+1]

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
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
for i in range(n):
    c[i] = a[i]+i
cb = Counter(b)
cc = Counter(c)
k=cb.keys()
ans = 0
for i in k:
    ans += cb[i]*cc[i*(-1)]
print(ans)

Submission status: Accepted

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

cnt = [0] * (2*(10 ** 5) + 10) 
for i in range(N):
    if A[i]+i >= 2*(10 ** 5):
        continue
    cnt[A[i]+i] += 1

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

print(ans)

Submission status: Accepted

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


list = [0] * (n-1)

ans = 0

for i in range(n):
    if a[i] + n - 1 - i > 0 and a[i] + n - 1 - i < n-1:
        ans += list[a[i] + n - 1 - i ]
    if a[i] < n - 1 - i: 
        list[n - 1 - a[i] - i] += 1

print(ans)

Submission status: Accepted

Solution code:
N, = map(int, input().split())
X = list(map(int, input().split()))
A = X[:]
B = X[:]
for i in range(N):
    A[i] += i+1
    B[i] -= i+1
d = dict()
for i in range(N):
    x = -A[i]
    if x not in d:
        d[x] = 0
    d[x] += 1
r = 0
for b in B:
    if b in d:
        r += d[b]
print(r)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

A = [int(v) for v in input().split()]
m = {}
count = 0

for i, a in enumerate(A):
    j = i - a
    if j >= 0 and j in m:
        count += m[j]

    k = a + i
    if k in m:
        m[k] += 1
    else:
        m[k] = 1

print(count)

Submission status: Accepted

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

plus = deque()
minus = deque()
for i in range(N):
    plus.append(i+A[i])
    minus.append(-A[i]+i)
p = Counter(plus)
m = Counter(minus)
key = p.keys()

cnt = 0
for k in list(key):
    # print(p[k])
    cnt += p[k]*m[k]

# print(p,m)
print(cnt)

Submission status: Accepted

Solution code:
n=int(input())

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

needsearch=[]

for i in range(n):
    a[i]-=(i+1)
    needsearch.append(-2*(i+1)-a[i])

counter=[0]*(2*(10**6))

for i in range(n):
    if 0<a[i]+10**6<2*(10**6):
        counter[a[i]+10**6]+=1

ans = 0
for i in range(len(needsearch)):
    if 0<needsearch[i]+10**6<2*(10**6):
        ans += counter[needsearch[i]+10**6]
    if 0<a[i]+10**6<2*(10**6):
        counter[a[i]+10**6]-=1


print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from collections import defaultdict
N=int(sys.stdin.readline().strip())
A=map(int, sys.stdin.readline().split())
C=defaultdict(lambda: 0)
ans=0
for i,a in enumerate(A):
    ans+=C[i-a]
    C[a+i]+=1
print ans

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = list(map(int,input().split()))
B = [A[k]+k for k in range(N)]
C = [k-A[k] for k in range(N)]
C = Counter(C)
ans = 0
for e in B:
    ans += C[e]
print(ans)

Submission status: Accepted

Solution code:
import collections
n = int(input())
l = list(map(int,input().split()))
k = []
for i in range(n):
    k.append(i+1+l[i])
c = collections.Counter(k)
cnt = 0
for i in range(n):
    cnt += c[i+1-l[i]]
print(cnt)

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] = i + 1 - A[i]
    C[i] = i + 1 + A[i]
for i in range(N):
    if B[i] < 0:
        B[i] = 200001
    if C[i] > N:
        C[i] = 200001
K = [0]*200002
L = [0]*200002
for i in B:
    K[i] += 1
for i in C:
    L[i] += 1
M = [0]*200001
for i in range(200001):
    M[i] = K[i]*L[i]
print(sum(M))

Submission status: Accepted

Solution code:
import sys

def main():
    N = int(input())
    A_list = list(map(int, input().split()))

    h_list = [0] * N

    for i, i_A in enumerate(A_list):
        if i - i_A >= 0:
            h_list[i-i_A] += 1

    total_pair = 0
    for i, i_A in enumerate(A_list):
        if i+i_A <= N-1:
            total_pair += h_list[i+i_A]

    print(total_pair)
    return
    
if __name__ == '__main__':
    main()
    sys.exit(0)

Submission status: Accepted

Solution code:
def mws5(lookup, hs):
    ans = 0
    for i in range(len(hs)):
        h = hs[i]
        ans += lookup[i+h]
    print(ans)

if __name__ == "__main__":
    import sys
    from collections import defaultdict as DD
    lookup = DD(int)  
    n = int(input())
    hs = [int(_) for _ in input().split()]
    for i, h in enumerate(hs):
        lookup[i-h] += 1
    mws5(lookup, hs)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# モジュールのインポート
import collections

# 標準入力の取得
N = int(input())
A = list(map(int, input().split()))

# 求解処理
# A_i + i = -A_j + j (i < j)
left = [A[i] + i for i in range(N)]
right = collections.Counter([-A[j] + j for j in range(N)])
result = 0
for l in left:
    result += right[l]

# 結果出力
print(result)

Submission status: Accepted

Solution code:
n = int(input())
li = list(map(int,input().split()))
li2 = [0] * n
li3 = [0] * n
cnt = 0
for i in range(len(li)):
    if i + li[i] < len(li):
        li2[i + li[i]] += 1
    if i - li[i] >= 0:
        li3[i - li[i]] += 1

for i in range(len(li)):
    if li2[i] > 0 and li3[i] > 0:
        cnt += li2[i] * li3[i]

print(cnt)

Submission status: Accepted

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

cnt1 = {}
cnt2 = {}

for i in range(N):
    tmp1 = A[i] + i + 1
    tmp2 = i + 1 - A[i]
    if tmp1 not in cnt1:
        cnt1[tmp1] = 1
    else:
        cnt1[tmp1] += 1
    if tmp2 not in cnt2:
        cnt2[tmp2] = 1
    else:
        cnt2[tmp2] += 1

diff = set(list(cnt1.keys())) & set(list(cnt2.keys()))

ans = 0
for d in diff:
    ans += cnt1[d] * cnt2[d]
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

A = list(map(int, input().split()))
check = {}
ans = 0


for i, v in enumerate(A):
    if (i-v) in check:
        ans += check[i-v]
    if v+i in check:
        check[v+i] += 1
    else:
        check[v+i] = 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import re
import math
from collections import defaultdict
import itertools
from copy import deepcopy
import random
from heapq import heappop,heappush
import time
import os
import queue
import sys
import datetime
from functools import lru_cache
#@lru_cache(maxsize=None)
readline=sys.stdin.readline
sys.setrecursionlimit(2000000)
#import numpy as np
alphabet="abcdefghijklmnopqrstuvwxyz"
mod=int(10**9+7)
inf=int(10**20)
def yn(b):
    if b:
        print("yes")
    else:
        print("no")
def Yn(b):
    if b:
        print("Yes")
    else:
        print("No")
def YN(b):
    if b:
        print("YES")
    else:
        print("NO")
class union_find():
    def __init__(self,n):
        self.n=n
        self.P=[a for a in range(N)]
        self.rank=[0]*n
 
    def find(self,x):
        if(x!=self.P[x]):self.P[x]=self.find(self.P[x])
        return self.P[x]
 
    def same(self,x,y):
        return self.find(x)==self.find(y)
 
    def link(self,x,y):
        if self.rank[x]<self.rank[y]:
            self.P[x]=y
        elif self.rank[y]<self.rank[x]:
            self.P[y]=x
        else:
            self.P[x]=y
            self.rank[y]+=1
 
    def unite(self,x,y):
        self.link(self.find(x),self.find(y))
 
    def size(self):
        S=set()
        for a in range(self.n):
            S.add(self.find(a))
        return len(S)
def is_power(a,b):#aはbの累乗数か
    now=b
    while now<a:
        now*=b
    if now==a:return True
    else:return False
def bin_(num,size):
    A=[0]*size
    for a in range(size):
        if (num>>(size-a-1))&1==1:
            A[a]=1
        else:
            A[a]=0
    return A
def get_facs(n,mod_=0):
    A=[1]*(n+1)
    for a in range(2,len(A)):
        A[a]=A[a-1]*a
        if(mod>0):A[a]%=mod_
    return A
def comb(n,r,mod,fac):
    if(n-r<0):return 0
    return (fac[n]*pow(fac[n-r],mod-2,mod)*pow(fac[r],mod-2,mod))%mod
def next_comb(num,size):
    x=num&(-num)
    y=num+x
    z=num&(~y)
    z//=x
    z=z>>1
    num=(y|z)
    if(num>=(1<<size)):return False
    else:
        return num
def get_primes(n,type="int"):
    A=[True]*(n+1)
    A[0]=False
    A[1]=False
    for a in range(2,n+1):
        if A[a]:
            for b in range(a*2,n+1,a):
                A[b]=False
    if(type=="bool"):return A
    B=[]
    for a in range(n+1):
        if(A[a]):B.append(a)
    return B
def is_prime(num):
    if(num<=2):return False
    i=2
    while i*i<=num:
       if(num%i==0):return False
       i+=1
    return True
def ifelse(a,b,c):
    if a:return b
    else:return  c
def join(A,c=" "):
    n=len(A)
    A=list(map(str,A))
    s=""
    for a in range(n):
        s+=A[a]
        if(a<n-1):s+=c
    return s
def factorize(n,type_="dict"):
    b = 2
    list_ = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            list_.append(b)
        b+=1
    if n > 1:list_.append(n)
    if type_=="dict":
        dic={}
        for a in list_:
            if a in dic:
                dic[a]+=1
            else:
                dic[a]=1
        return dic
    elif type_=="list":
        return list_
    else:
        return None
def floor_(n,x=1):
    return x*(n//x)
def ceil_(n,x=1):
    return x*((n+x-1)//x)
def hani(x,min_,max_):
    ret=x
    if x<min_:ret=min_
    if x>max_:ret=max_
    return ret
def seifu(x):
    return x//abs(x)
###################################################

def main():
    n=int(input())
    A=list(map(int,input().split()))
    ans=0
    jmAj=defaultdict(int)
    ipAi=defaultdict(int)
    for i in range(len(A)):
        ipAi[str(A[i]+i)]+=1

    for i in range(len(A)-1,-1,-1):
        num=A[i]+i
        ans+=jmAj[str(A[i]+i)]
        jmAj[str(i-A[i])]+=1
    print(ans)
main()

Submission status: Accepted

Solution code:
input = raw_input

from collections import Counter
n = int(input())
As = map(int, input().split(" "))

Bs = [i-A for i, A in enumerate(As)]

c = Counter(Bs)
out = 0
for i in range(n):
    key = As[i] + i 
    cur_out = c[key]
    out += cur_out

print(out)

Submission status: Accepted

Solution code:
from sys import stdin

N = int(stdin.readline().rstrip())
A = [int(x) for x in stdin.readline().rstrip().split()] 

A_minus = []
A_plus = []

for i in range(N):
    A_plus.append(i+A[i])
    A_minus.append(i-A[i])

A_plus.sort()
A_minus.sort()

tot = 0
index = 0

a_prev = A_plus[0]
A_plus_map = {}
A_plus_map[a_prev] = 1
for i in range(1,N):
    a = A_plus[i]
    if a == a_prev:
        A_plus_map[a] += 1
    else:
        A_plus_map[a] = 1
        a_prev= a



a_prev = A_minus[0]
A_minus_map = {}
A_minus_map[a_prev] = 1
for i in range(1,N):
    a = A_minus[i]
    if a == a_prev:
        A_minus_map[a] += 1
    else:
        A_minus_map[a] = 1
        a_prev= a


tot = 0
for key in A_plus_map.keys():
    val = A_plus_map[key]
    if key in A_minus_map.keys():
        tot += val * A_minus_map[key]

print(tot)

Submission status: Accepted

Solution code:
a = int(input())
lis = list(map(int, input().split()))
lis2 = []
d = {}
cnt=1
for i in lis:
    if(lis[cnt-1]-cnt in d):
        d[lis[cnt-1]-cnt]=d[lis[cnt-1]-cnt]+1
    else:
        d[lis[cnt - 1] - cnt] = 1
    cnt+=1
cnt=1
result=0
for i in lis:
    if(-cnt-i in d):
        result+=d[-cnt-i]
    cnt += 1
print(result)

Submission status: Accepted

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

p=defaultdict(int)
q=defaultdict(int)

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

ans=0
for k,v in p.items():
    x=q[k]
    ans+=x*v
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
c=0
x=[]
y={}
for i in range(n):
	x.append(l[i]+i)
	if (i-l[i]) in y: 
		y[i-l[i]]+=1
	else:
		y[i-l[i]]=1
for i in x:
	if i in y :
		c+=y[i]

	
print(c)

Submission status: Accepted

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

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

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

    a=A[i]+i+1
    if a not in dp:
        dp[a]=1
    else:
        dp[a]+=1

  

print(ans)