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,bisect,string,math,time,functools,random
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
from itertools import permutations,combinations,groupby
def Golf():*a,=map(int,open(0))
def I():return int(input())
def S_():return input()
def IS():return input().split()
def LS():return [i for i in input().split()]
def LI():return [int(i) for i in input().split()]
def LI_():return [int(i)-1 for i in input().split()]
def NI(n):return [int(input()) for i in range(n)]
def NI_(n):return [int(input())-1 for i in range(n)]
def StoLI():return [ord(i)-97 for i in input()]
def ItoS(n):return chr(n+97)
def LtoS(ls):return ''.join([chr(i+97) for i in ls])
def GI(V,E,ls=None,Directed=False,index=1):
    org_inp=[];g=[[] for i in range(V)]
    FromStdin=True if ls==None else False
    for i in range(E):
        if FromStdin:
            inp=LI()
            a,b,c=(inp+[1])[:3]
            org_inp.append(inp)
        else:
            index=0
            a,b,c=(ls[i]+[1])[:3]
        if index==1:a-=1;b-=1
        aa=(a,c);bb=(b,c);g[a].append(bb)
        if not Directed:g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0},boundary=1):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[boundary]*(w+2);found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[boundary]+[mp_def[j] for j in s]+[boundary]
    mp+=[boundary]*(w+2)
    return h+2,w+2,mp,found
def TI(n):return GI(n,n-1)
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)];rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:print(*inp,end=end)

YN=['YES','NO'];Yn=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()

class Comb:
    def __init__(self,n,mo=10**9+7):
        self.fac=[0]*(n+1)
        self.inv=[1]*(n+1)
        self.fac[0]=1
        self.fact(n)
        for i in range(1,n+1):
            self.fac[i]=i*self.fac[i-1]%mo
            self.inv[n]*=i
            self.inv[n]%=mo
        self.inv[n]=pow(self.inv[n],mo-2,mo)
        for i in range(1,n):
            self.inv[n-i]=self.inv[n-i+1]*(n-i+1)%mo
        return
    
    def fact(self,n):
        return self.fac[n]
        
    def invf(self,n):
        return self.inv[n]

    def comb(self,x,y):
        if y<0 or y>x:
            return 0
        return self.fac[x]*self.inv[x-y]*self.inv[y]%mo

class Tree:
    def __init__(self,inp_size=None,init=True):
        if init:
            self.stdin(inp_size)
        return

    def stdin(self,inp_size=None):
        if inp_size==None:
            self.size=int(input())
        else:
            self.size=inp_size
        self.edges,_=GI(self.size,self.size-1)
        return
    
    def listin(self,ls):
        self.size=len(ls)+1
        self.edges,_=GI(self.size,self.size-1,ls)
        return

    def __str__(self):
        return  str(self.edges)

    def dfs(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append(x)
        v=[-1]*self.size
        v[x]=root_v
        while q:
            c=q.pop()
            for nb,d in self.edges[c]:
                if v[nb]==-1:
                    q.append(nb)
                    v[nb]=func(v[c],nb,d)
        return v

    def EulerTour(self,x,func=lambda prv,nx,dist:prv+dist,root_v=0):
        q=deque()
        q.append((-1,x))
        v=[None]*self.size
        v[x]=root_v
        et=[]
        while q:
            cb,ce=q.pop()
            et.append(ce)
            for nb,d in self.edges[ce]:
                if v[nb]==None:
                    q.append((nb,ce))
                    q.append((ce,nb))
                    v[nb]=func(v[ce],nb,d)
        vid=[[-1,-1]for i in range(self.size)]
        for i,j in enumerate(et):
            if vid[j][0]==-1:
                vid[j][0]=i
            else:
                vid[j][1]=i
        return v,et,vid
    
    def LCA_init(self,depth,et):
        self.st=SegTree(self.size*2-1,func=min,ide=inf)
        for i,j in enumerate(et):
            self.st.update(i,j)
        self.LCA_init_stat==True
        return
    
    def LCA(self,root,x,y):
        if self.LCA_init_stat==False:
            depth,et,vid=self.EulerTour(root)
            self.LCA_init(depth,et)
        return self.st.query(x,y+1)

show_flg=False
show_flg=True

n=I()
a=LI()
m=[]
p=[]
ans=0

z=defaultdict(int)
for i in range(n):
    ans+=z[a[i]-i]
    z[-a[i]-i]+=1
print(ans)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
n, *a = map(int, open(0).read().split())
x = [[0, 0] for i in range(n)]
for i in range(n):
    if 0<=i-a[i]<n: x[i-a[i]][0] += 1
    if 0<=i+a[i]<n: x[i+a[i]][1] += 1
ans = 0
for y in x:
    ans += y[0] * y[1]
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
from collections import deque, defaultdict
from itertools import combinations, combinations_with_replacement
import bisect
from math import factorial, sqrt, log, ceil, floor

def main():
    #N, M = map(int, input().split())
    N = int(input())
    As = list(map(int, input().split()))

    d = defaultdict(int)
    for i, a in enumerate(As):
        key = i - a
        d[key] += 1

    cnt = 0
    for i, a in enumerate(As):
        key = i + a
        cnt += d[key]

    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int, input().split()))
ans = 0
d = {}
d[1 - A[0]] = 1
base1 = 0
base2 = 1
for a in A[1:]:
    _a = a - base1
    _a_ = 1 - a - base2
    if _a in d:
        ans += d[_a]
    if _a_ in d:
        d[_a_] += 1
    else:
        d[_a_] = 1
    base1 += 1
    base2 += 1

print(ans)

Submission status: Accepted

Solution code:
import collections
def main():

    N = int(input())
    A = list(map(int, input().split()))
    d = collections.defaultdict(int)
    ans = 0
    for j in range(N):
        if A[j] - (j+1) in d:
            ans += d[A[j]-(j+1)]
        d[-(j+1)-A[j]] += 1
    return ans


if __name__ == '__main__':
    print(main())

Submission status: Accepted

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math


NN = 202020
MOD = 10**9+7
# MOD = 998244353
INF = float("inf")

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

seen = defaultdict(int)
count = 0
for i in range(n):
    count += seen[A[i]-i]
    seen[-A[i]-i] += 1
    # print(i, A[i]-i, count, seen)

print(count)

Submission status: Accepted

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

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

a.insert(0, 0)
c = dict()
c[1 + a[1]] = 1
cnt = 0

for x in range(2, n + 1):
    if x - a[x] in c.keys():
        cnt += c[x - a[x]]

    if x + a[x] < 0:
        continue

    if x + a[x] in c.keys():
        c[x + a[x]] += 1
    else:
        c[x + a[x]] = 1

print(cnt)

Submission status: Accepted

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

c = [i - v for i, v in enumerate(a)]
check = Counter(c)
ans = 0
for i, v in enumerate(a):
    ans += check[i + v]
print(ans)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)

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

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

CNT = [0] * (10 ** 7)

ans = 0
for i in range(N):
    a = A[i]
    p = i - a

    if 0 <= p <= (10 ** 7):
        ans += CNT[p]

    if 0 <= i + a <= (10 ** 7):
        CNT[i + a] += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
from math import log2,floor,ceil,sqrt
# import bisect
# from collections import deque

Ri = lambda : [int(x) for x in sys.stdin.readline().split()]
ri = lambda : sys.stdin.readline().strip()
 
def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
INF = 10 ** 18
MOD = 10**9+7

n = int(ri())
a = Ri()

dic = {}
cnt = 0
for i in range(len(a)):
    if (i+1)-a[i] > 0 and (i+1)-a[i] in dic:
        cnt+=dic[(i+1)-a[i]]

    if i+1+a[i] in dic:
        dic[i+1+a[i]]+=1
    else:
        dic[i+1+a[i]] = 1
print(cnt)

Submission status: Accepted

Solution code:
import sys,math,copy,queue,itertools,bisect,collections
from heapq import *
sys.setrecursionlimit(10**7)
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())
INF = 10**18
MOD = 10**9 + 7
DD = ((1,0),(-1,0),(0,1),(0,-1))

N = NI()
A = [0] + LI()

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

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

Submission status: Accepted

Solution code:
def main():
    import sys 
    input=sys.stdin.readline 
    n=int(input())
    A=list(map(int,input().split()))
    
    dp1={}
    dp2={}
    for i in range(n):
        try:dp1[i+1+A[i]]+=1
        except:
            dp1[i+1+A[i]]=1
        if i+1>A[i]:
            try:dp2[i+1-A[i]]+=1
            except:
                dp2[i+1-A[i]]=1
        
    cnt=0
    
    #print(dp1)
    #print(dp2)
    for i in dp1:
        try:
            cnt+=dp1[i]*dp2[i]
        except:
            cnt+=0
    print(cnt)

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from collections import*
n,*a=map(int,open(0).read().split())
o=[];t=[]
for i,x in enumerate(a):o+=i+x,;t+=i-x,
f=lambda l:sum(x*(x-1)//2 for x in Counter(l).values())
print(f(o+t)-f(o)-f(t))

Submission status: Accepted

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

d = {}
ans = 0
for i in range(n):
    if i-A[i] in d:
        ans += d[i-A[i]]
    if A[i]+i not in d:
        d[A[i]+i] = 1
    else:
        d[A[i]+i] += 1
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

L=[0]*(10**6)
for i in range(N):
    if i-A[i]>=0:
        L[i-A[i]]+=1
ans=0
for i in range(N):
    tall=A[i]
    if tall+i<len(L):
        ans+=L[tall+i]
print(ans)
#print(L[:10])

Submission status: Accepted

Solution code:
import sys
from collections import Counter

read = sys.stdin.read
readline = sys.stdin.readline

N, *A = map(int, read().split())
p = Counter([i + idx for idx, i in enumerate(A, 1)])
m = Counter([i - idx for idx, i in enumerate(A, 1)])
answer = 0

for i, j in p.items():
    answer += j * m[-i]

print(answer)

Submission status: Accepted

Solution code:
from math import sqrt,ceil,floor
def mi():return map(int,input().split())
def li():return list(mi())
def ii():return int(input())



n=ii()
a=li()
x=[]
m={}
for i in range(1,n+1):
    x1=a[i-1]-i
    x.append(x1)
    
    if x1 not in m:
        m[x1]=1
    else:
        m[x1]+=1
        
ans=0
for i in range(n):
    x1=x[i]-2*a[i]
    
    
    if x1 in m:
        ans+=m[x1]
        
print(ans)

Submission status: Accepted

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

def solve_(n, A):
    tmp = {}
    for i, a in enumerate(A):
        v = i + a
        if not v in tmp:
            tmp[v] = 0
        tmp[v] += 1
    ret = 0
    for i, a in enumerate(A):
        t = i - a
        if t >= 0 and t in tmp:
            ret += tmp[t]
    return ret

def solve(n, A):
    ret = solve_(n, A) + solve_(n, A[::-1])
    print(ret // 2)
    return ret

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

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
d = {}

arr = list(map(int,input().split()))
ans = 0
for i in range(n):
    diff = i+1-arr[i]
    if diff in d:
        ans += d[diff]

    ss = i+1 +arr[i]
    if ss in d:
        d[ss] += 1
    else:
        d[ss] = 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
from collections import defaultdict


def main():
    n = int(input().strip())
    a_list = list(map(int, input().split()))

    p_set = defaultdict(set)
    n_set = defaultdict(set)

    for i, a in enumerate(a_list):
        p_set[a_list[i] - i].add(i)
        n_set[- a_list[i] - i].add(i)

    r = 0
    for p in p_set:
        pl = len(p_set[p])
        nl = len(n_set[p])
        r += pl * nl
    print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

import sys
from collections import Counter

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N = INT()
A = LIST()

B = [0] * N
for i in range(N):
    B[i] = A[i] - i
C = Counter(B)
offset = 0
ans = 0
for i in range(N-1):
    C[B[i]] -= 1
    ans += C[-A[i]+offset]
    offset -= 1
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
from bisect import bisect_left, bisect_right

n = int(input())
a = list(map(int, input().split()))
m = sorted(i - x for i, x in enumerate(a))
p = sorted(i + x for i, x in enumerate(a))
cs = [0] * 10 ** 6
ans = 0
for i in range(n):
    if m[i] <= 0:
        continue
    ans += bisect_right(p, m[i], 0, i) - bisect_left(p, m[i], 0, i)
print(ans)

Submission status: Accepted

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

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
D_sub=defaultdict(int)
D_add=defaultdict(int)
ans_2=0
for i,a in enumerate(A,1):
    SUB=i-a
    ans_2 += D_sub[SUB]
    D_sub[i+a]+=1

print(ans_2)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
ns = list(map(int, input().split()))
xma = [x - a for x, a in enumerate(ns)]
xpa = [x + a for x, a in enumerate(ns)]
m = Counter(xma)
p = Counter(xpa)
cnt = 0
for key, value in m.items():
    if key in p:
        cnt += value * p[key]
print(cnt)

Submission status: Accepted

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

tasi=[0]*n
hiki=[0]*n

for i in range(n):
    wa=i+a[i]
    sa=i-a[i]
    if(wa<n):
        tasi[wa]+=1
    if(sa>=0):
        hiki[sa]+=1

ans=0

for i in range(n):
    ans+=tasi[i]*hiki[i]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
B = [A[i]+i for i in range(N)]
C = [i-A[i] for i in range(N)]
d1 = defaultdict(lambda:0)
d2 = defaultdict(lambda:0)
for b in B:
    d1[b] += 1
for c in C:
    d2[c] += 1
ans = 0
for b in d1:
    ans += d1[b]*d2[b]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

R = {}

for i in range(1 , N):
  t = A[0] + A[i] - i
  if t in R:
    R[t] += 1
  else:
    R[t] = 1

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

ct = Counter(a - i for i, a in enumerate(A))
ans = 0
for i, a in enumerate(A):
    ans += ct[-a - i]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


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

hs = defaultdict(int)
cnt = 0

for i, height in enumerate(al):
    num = i + 1
    if i-height in hs:
        cnt += hs[i-height]
    hs[i+height] += 1
print(cnt)

Submission status: Accepted

Solution code:
from collections import defaultdict
n=int(input())
A=[int(i) for i in input().split()]
d=defaultdict(int)

b=[A[i] - (i+1) for i in range(n)]
c=[A[i] + (i+1) for i in range(n)]

l=[]
ans=0
d=defaultdict(int)
for i in range(1,n)[::-1]:
    d[c[i]]+=1
    d[b[i]]+=1
    ans+= d[-c[i-1]]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections

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

result = 0
ai = [0]*n
aj = [0]*n

for i in range(n):
    ai[i] = a[i]+i+1
    aj[i] = i+1-a[i]
aj_num = collections.Counter(aj)
    
for i in range(n-1):
    aj_num[aj[i]] -= 1
    result += aj_num[ai[i]]
    
print(result)

Submission status: Accepted

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n = int(input())

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

bi = [0] * n
ci = [0] * n

for i, aa in enumerate(ai):
    bi[i] = aa + i
    ci[i] = aa - i

# print(bi)

bi_dict = {}
ci_dict = {}
for i in range(n):
    bi_dict[bi[i]] = bi_dict.get(bi[i], 0) + 1
    ci_dict[ci[i]] = ci_dict.get(ci[i], 0) + 1

ans = 0
for b in bi_dict:
    ans += bi_dict[b] * ci_dict.get(-b, 0)
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

li1 = [i+1-A[i] for i in range(N)]
li2 = [A[i]+i+1 for i in range(N)]

cnt = [0 for i in range(2*N+1)]
for i in li2:
    if i<len(cnt)-1:
        cnt[i] += 1

ans = 0
for i in li1:
    if i>=0:
        ans += cnt[i]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,Counter
N = int(input())
A = [int(c) for c in input().split()]
B = [c-i for i,c in enumerate(A)]
dic = defaultdict(int)
Cnt = Counter(B)
ans = 0
for i,c in enumerate(B):
  dic[c] += 1
  ans += Cnt[-2*i-c]-dic[-2*i-c]
print(ans)

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    d = {}
    r = 0
    for i, v in enumerate(A, start = 1):
        if -i-v in d:
            d[-i-v] += 1
        else:
            d[-i-v] = 1
        if v-i in d:
            r += d[v-i]
    return r
print(main())

Submission status: Accepted

Solution code:
N = int(input())
Attendees = list(map(int, input().split()))
Groups = [[0,0] for _ in range(N)]
for pos, number in enumerate(Attendees):
    if pos - number >= 0:
        Groups[pos - number][0] += 1

    if pos + number < N:
        Groups[pos + number][1] += 1

ans = 0
for elt in Groups:
    ans += elt[0] * elt[1]
print(ans)

Submission status: Accepted

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

N = int(input())
A = list(map(int, input().split()))
ans = 0
cnt = defaultdict(int)

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

print(ans)

Submission status: Accepted

Solution code:
import collections

n = int(input())
a = [int(i) for i in input().split()]
a_i = [i - aa for i, aa in enumerate(a)]
a_j = [j + aa for j, aa in enumerate(a)]

ci = collections.Counter(a_i)
cj = collections.Counter(a_j)
ans = 0
for item, value in ci.items():
    if item in cj.keys():
        ans += cj[item] * ci[item]
print(ans)

Submission status: Accepted

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

s = [i + 1 + a[i] for i in range(n)]
dic = {}
for i in range(n):
    d = i + 1 - a[i]
    if d in dic:
        dic[d] += 1
    else:
        dic[d] = 1
ans = sum([dic[si] if si in dic else 0 for si in s])
print(ans)

Submission status: Accepted

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

al_m = [i - idx for idx, i in enumerate(al)]
al_m2 = [-i - idx for idx, i in enumerate(al)]

al_p = [i + idx for idx, i in enumerate(al)]
al_p2 = [-i + idx for idx, i in enumerate(al)]

from collections import defaultdict
dic = defaultdict(int)

ans = 0
for a in al_m:
    dic[a] += 1
for a in al_m2:
    ans += dic[a]

dic = defaultdict(int)
for a in al_p:
    dic[a] += 1
for a in al_p2:
    ans += dic[a]

print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
cnt1 = {}
cnt2 = {}
for i in range(n):
    x = a[i] + i
    y = i- a[i]
    if x not in cnt1:cnt1[x] = 1
    else:cnt1[x] += 1
    if y not in cnt2:cnt2[y] = 1
    else:cnt2[y] += 1
ans = 0
for num in cnt1:
    if num not in cnt2:continue
    x = cnt2[num]
    ans += x*cnt1[num]
for num in cnt2:
    if num not in cnt1:continue
    x = cnt1[num]
    ans += x*cnt2[num]
ans //= 2
print(ans)

Submission status: Accepted

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

# O(N)
cnt = 0
starts = [0 for _ in range(n)]
for i, v in enumerate(a):
    next_idx = v + i + 1
    if next_idx < n:
        starts[next_idx] += 1
    if 0 <= i - v + 1 <= n-1:
        cnt += starts[i - v + 1]
print(cnt)

Submission status: Accepted

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

d = {}
res = 0
for _i, a in enumerate(A):
    i = _i + 1
    if i - a in d:
        res += d[i - a]
    d[a + i] = 1 if a + i not in d else d[a+i] + 1

print(res)

Submission status: Accepted

Solution code:
from collections import Counter

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

B = [0]*N
for i in range(N):
    B[i] = i - A[i]

C = Counter(B)

ans = 0
for j in range(N-1):
    d = A[j]+j
    ans += C[d]
    C[B[j]] -= 1

print(ans)

Submission status: Accepted

Solution code:
n=int(input())
A=[int(i) for i in input().split()]
r=[0 for i in range(n)]
l=[0 for i in range(n)]

for i in range(n):
    if A[i]+i<n:
        r[A[i]+i]+=1
    if i-A[i]>=0:
        l[i-A[i]]+=1

ans=0
for i in range(n):
    ans+=r[i]*l[i]
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

def main():
    mod=10**9+7
    N=I()
    A=LI()
    
    from collections import defaultdict
    dd1 = defaultdict(int)
    dd2 = defaultdict(int)
    
    for i in range(N):
        dd1[A[i]+i]+=1
        dd2[i-A[i]]+=1
        
    ans=0    
    for k,v in dd1.items():
        ans+=v*dd2[k]
        
    print(ans)
    
main()

Submission status: Accepted

Solution code:
from collections import Counter

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

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

ans = 0
for L in range(N):
    AL = As[L]
    cnt[L-AL] -= 1
    ans += cnt[L+AL]

print(ans)

Submission status: Accepted

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

sum_dict = {}
diff_dict = {}
for i in range(N):
    try:
        sum_dict[i + A[i]] += 1
    except:
        sum_dict[i + A[i]] = 1
    try:
        diff_dict[i - A[i]] += 1
    except:
        diff_dict[i - A[i]] = 1
ans = 0
for key in sum_dict:
    try:
        ans += sum_dict[key] * diff_dict[key]
    except:
        pass
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
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 LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def main():
    cnt=defaultdict(int)
    n=II()
    aa=LI()
    pp=[]
    mm=[]
    for i,a in enumerate(aa):
        pp.append(i+aa[i])
        mm.append(i-aa[i])
    #print(pp)
    #print(mm)
    ans=0
    for p,m in zip(pp[::-1],mm[::-1]):
        ans+=cnt[p]
        if m>0:cnt[m]+=1
    print(ans)

main()

Submission status: Accepted

Solution code:
import collections
N = int(input())
A = [int(_) for _ in input().split()]
B = [v - i for i, v in enumerate(A)]
C = collections.Counter(B)
ans = 0
for i, b in enumerate(B):
    C[b] -= 1
    ans += C[-(b + 2 * i)]
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as dd
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = a[: ]
res = 0
for i in range(N): b[i] -= i
d = dd(list)
for i in range(N): d[b[i]].append(i)
for i in range(N):
  x = b[i] + i * 2
  j = bl(d[-x], i)
  res += len(d[-x]) - j
print(res)

Submission status: Accepted

Solution code:
import bisect
n = int(input())
a = list(map(int, input().split()))
ans = 0
l_dp = []
r_dp = []
for i in range(n):
    l_dp.append(a[i]+i)
    r_dp.append(n-i-1-a[n-i-1])
r_dp.sort()
for i in l_dp:
    if i < 0 or i >= n: continue
    l_index = bisect.bisect_left(r_dp, i)
    r_index = bisect.bisect_right(r_dp, i)
    ans += r_index - l_index
print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import math
import sys
from collections import *
from itertools import accumulate, combinations, permutations, product
from math import gcd
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

ans=0
dic=defaultdict(int)

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

Submission status: Accepted

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

Dic1={}
set1=set()
for i in range(1,N+1):
    temp=i-A[i]
    if temp in set1:
        Dic1[temp]=Dic1[temp]+1
    else:
        Dic1[temp]=1
        set1.add(temp)

#print(Dic1)

Dic2={}
set2=set()
for j in range(1,N+1):
    temp=j+A[j]
    if temp in set2:
        Dic2[temp]=Dic2[temp]+1
    else:
        Dic2[temp]=1
        set2.add(temp)

#print(Dic2)


ans=0
for k in range(len(set1)):
    now=set1.pop()
    if now in set2:
        ans+=Dic1[now]*Dic2[now]

print(ans)