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:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
from bisect import bisect_left,bisect_right 
import sys,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = inp()
a = inpl()
sa = defaultdict(int)
for i,x in enumerate(a):
    sa[(i+1)-x] += 1
res = 0
for i,x in enumerate(a):
    res += sa[i+1+x]
print(res)

Submission status: Accepted

Solution code:
from collections import Counter

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

li1 = [i + e for i, e in enumerate(a, 1)]
li2 = [i - e for i, e in enumerate(a, 1)]

c1 = Counter(li1)
c2 = Counter(li2)

ans = 0
for k, v in c1.items():
    v2 = c2[k]
    ans += v * v2

print(ans)

Submission status: Accepted

Solution code:
N = int(input())

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

dict_ = {}

ans = 0
for i in range(N):
  k = (i+1) - A[i]
  if k in dict_:
    ans += dict_[k]
  ad = (i+1) + A[i]
  if ad in dict_:
    dict_[ad] = dict_[ad] + 1
  else:
    dict_[ad] = 1

print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int, input().split()))

count = 0
dict_height = {}

for i in range(N):
  target = i+1-A[i]
  if target in dict_height.keys():
    count += dict_height[target]
  height = i+1+A[i]
  if height in dict_height.keys():
    dict_height[height] += 1
  else:
    dict_height[height] = 1

print(count)

Submission status: Accepted

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

B = {}

for i in range(N):
    # B.append(A[i] - i - 1)
    c = i + 1 - A[i]
    if c not in B.keys():
        B[c] = 1
    else: B[c] += 1
# print(A)
# print(B)

ans = 0
for i in range(N):
    c = A[i] + i + 1
    if c in B.keys():
        ans += B[c]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
N = int(input())
d = defaultdict(list)
A = list(map(int, input().split()))
li = []
for i in range(N):
    a = A[i]
    li.append(i+a)
    d[i-a].append(i)
ans = 0
for x in li:
    ans += len(d[x])
print(ans)

Submission status: Accepted

Solution code:
n=int(input())
a=list(map(int,input().split()))
mem={}
for i in range(n):
    if i+1-a[i] not in mem:
        mem[i+1-a[i]]=[0,1]
    else:
        mem[i + 1 - a[i]][1]+=1
    if i+1+a[i] not in mem:
        mem[i+1+a[i]]=[1,0]
    else:
        mem[i+1+a[i]][0]+=1
s=0
mem2=list(mem.values())
for i in range(len(mem2)):
    s+=mem2[i][0]*mem2[i][1]
print(s)

Submission status: Accepted

Solution code:
#!python3

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


def main():
    d = {N - A[-1]: 1}
    ans = 0
    for i in range(N - 2, -1, -1):
        x = i + 1 + A[i]
        ans += 0 if x not in d else d[x]
        y = i + 1 - A[i]
        if y in d:
            d[y] += 1
        else:
            d[y] = 1
    
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import collections

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect

N = int(input())

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

T = defaultdict(list)
for i,a in enumerate(A):
    T[a-i].append(i)

cnt = 0
for i,a in enumerate(A):
    x = -a-i
    if x in T:
        l = T[x]
        cnt += len(l) - bisect(l, i)

print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int, input().split()))
i, j = [], []
for s in range(n):
    num = s+1
    i.append(a[s]+num)
    j.append(num-a[s])
x = Counter(j)
result = 0
for p in range(n-1):
    if i[p] in x:
        result += x[i[p]]
    x[j[p]] += 1 
print(result)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

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

n=n_in()
A=l_in()
B=[i-A[i] for i in range(n)]

from collections import Counter
c= Counter(B)

res = 0
for i in range(n):
    res += c[A[i]+i]

print(res)

Submission status: Accepted

Solution code:
# coding: utf-8
N=int(input())
A=list(map(int,input().split()))
L=[0 for i in range(N)]
R=[0 for i in range(N)]

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


print(ans)

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

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

#############
# Main Code #
#############

N = inputI()
A = inputIL()

a = [i-A[i] for i in range(N)]
b = [i+A[i] for i in range(N)]

key = list(set(a)|set(b))
dic = {k:0 for k in key}
for k in a:
  dic[k] += 1

ans = 0
for i in range(N):
  dic[a[i]] -= 1
  ans += dic[b[i]]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
############ ---- USER DEFINED INPUT FUNCTIONS ---- ############
def inp():
    return(int(input().rstrip()))
def inlt():
    return(list(map(int,input().rstrip().split())))
def insr():
    s = input().rstrip()
    return(s[:len(s) - 1])
def invr():
    return(map(int,input().rstrip().split()))
################################################################
n = inp()
nums = [0] + inlt()
num_dict = defaultdict(int)
cnt = 0
for i in range(1,n + 1):
    num_dict[i - nums[i]] += 1

for i in range(1,n + 1):
    ii = i + nums[i]
    jj = i - nums[i]
    if num_dict[jj] > 0:
        num_dict[jj] -= 1
    cnt += num_dict[ii]
    

print(cnt)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N = I()
    A = LI()
    aii = [0 for _ in range(N)]
    negajj = [0 for _ in range(N)]
    for i, a in enumerate(A):
        i += 1
        aii[i-1] = a + i
        negajj[i-1] = -(a - i)
    setaii = collections.Counter(aii)
    setnegajj = collections.Counter(negajj)
    cnt = 0
    for elem in aii:
        cnt += setnegajj[elem]
    print(cnt)
main()

Submission status: Accepted

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

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

l = [0] * len(A)
r = [0] * len(A)

for i,a in enumerate(A):
    if i - a >= 0:
        l[i - a] += 1
    if i + a < len(A):
        r[i + a] += 1

ans = 0

for x,y in zip(l, r):
    ans += x * y

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
A = list(map(int, input().split()))
B = [i+a for i, a in enumerate(A)]
C = [j-a for j, a in enumerate(A)]

bc = Counter(B)
cc = Counter(C)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


n = I()
A = list(range(1, n + 1))
B = LI()
ans = 0
D = defaultdict(int)
for i in range(n - 1):
    D[A[i] + B[i]] += 1
    ans += D[A[i + 1] - B[i + 1]]

D2 = defaultdict(int)
for i in range(n - 1, 0, -1):
    D2[A[i] - B[i]] += 1
    ans += D2[A[i - 1] + B[i - 1]]

print(ans // 2)

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect
def f():
    return []

d=defaultdict(f)
n=int(input())
a=list(map(int,input().split()))
x=[i+1+a[i] for i in range(n)]
y=[i+1-a[i] for i in range(n)]
for i in range(n):
    d[y[i]].append(i)

ans=0
for i in range(n):
    p=x[i]
    ans+=len(d[p])-bisect.bisect_right(d[p],i)
print(ans)

Submission status: Accepted

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

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

a_j = []
a_i = []

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

from collections import Counter

c1 = Counter(a_i)
c2 = Counter(a_j)
ans = 0
for c in c1.keys():
    ans += c1[c]*c2[c]
print(ans)

Submission status: Accepted

Solution code:
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))

from collections import defaultdict, Counter
from sys import exit
import math


def main():
    n = getN()
    nums = getList()
    den = [num - i for i, num in enumerate(nums)]
    cnt = Counter(den)
    ans = 0
    for i in range(n-1):
        k1, k2 = nums[i], nums[i+1]
        su = k1 + k2
        tgt = den[i+1] - su + 1
        if tgt in cnt.keys():
            ans += cnt[tgt]
    print(ans)
if __name__ == "__main__":
    main()

Submission status: Accepted

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
from collections import defaultdict


def main():
    N = int(input())
    A = list(map(int,input().split()))
    D = defaultdict(int)
    for i in range(N):
        D[A[i]+i] +=1
    s = 0
    for i in range(N):
        s += D[i-A[i]]
    print(s)
    pass

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int, input().split()))
plus = {}  # i + A[i]
minus = {}  # i - A[i]
for i in range(n):
    try:
        plus[i + a[i]] += 1
    except:
        plus[i + a[i]] = 1
    
    if i - a[i] > 0:
        try:
            minus[i - a[i]] += 1
        except:
            minus[i - a[i]] = 1

ans = 0
for key in plus.keys() & minus.keys():
    ans += plus[key] * minus[key]
print(ans)

Submission status: Accepted

Solution code:
def examA():
    S = SI()
    if S=="ARC":
        ans = "ABC"
    else:
        ans = "ARC"
    print(ans)
    return

def examB():
    N, K = LI()
    snuke = set(range(1,N+1))
    for _ in range(K):
        d = I()
        A = LI()
        for a in A:
            snuke.discard(a)
    ans = len(snuke)
    print(ans)
    return

def examC():
    N, M = LI()
    H = LI()
    good = set(range(1,N+1))
    for _ in range(M):
        a, b = LI()
        if H[a-1]>=H[b-1]:
            good.discard(b)
        if H[b-1]>=H[a-1]:
            good.discard(a)
    ans = len(good)
    print(ans)
    return

def examD():
    X = I()
    #print(1000**5-999**5)
    for a in range(-1000,1000):
        for b in range(-1000,1000):
            if a**5-b**5==X:
                print(a,b)
                return
    return

def examE():
    N = I()
    A = LI()
    B = [0]*N
    D = defaultdict(int)
    for i in range(N):
        B[i] = A[i]-i
        c = A[i]+i
        D[c] += 1
    #print(B)
    #print(D)
    ans = 0
    for b in B:
        ans += D[-b]
    print(ans)
    return

def examF():
    N, A, B, C = LI()
    S = [SI()for _ in range(N)]
    ans = [""]*N


    print(ans)
    return

import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(readline())
def LI(): return list(map(int,readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
n,*a=map(int,open(0).read().split())
b=[a[i]+(i+1) for i in range(n)]
c=[(i+1)-a[i] for i in range(n)]
k=set(b)&set(c)
b=Counter(b)
c=Counter(c)
ans=0
for i in k:
  ans+=b[i]*c[i]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter


def solve():
    n = int(input())
    a = list(map(int, input().split()))
    l1 = [i-a[i] for i in range(n)]
    l2 = [a[i]+i for i in range(n)]
    c1 = Counter(l1)
    c2 = Counter(l2)
    ans = 0
    for i in l1:
        ans += c2[i]
    print(ans)


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

n = int(input())
a = list(map(int, input().split()))
info = [0 for i in range(10**6)]
mid = 5*10**5

for i in range(n):
    if(a[i]<=2*10**5):
        num = a[i] - i
        info[mid + num] += 1
#print(info[mid-8:mid+8])
ans = 0
for i in range(n):
    if(a[i]<=2*10**5):
        num = a[i] - i
        ans += info[mid + num - a[i]*2]

print(ans)

Submission status: Accepted

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

res = 0
dic=dd(int)

for i in range(1,N):
    tmp = a[i]-i
    dic[tmp] += 1
for i in range(N-1):
    tgt = -a[i]-i
    res += dic[tgt]
print(res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import collections
import math
import operator as op
from functools import reduce
from collections import Counter
import numpy as np
import math
import bisect
import heapq


def get_inputs(cast_func=None):
    if cast_func is None:
        return input().split()
    else:
        return list(map(cast_func, input().split()))


def get_input(cast_func=None):
    if cast_func is None:
        return input()
    else:
        return cast_func(input())


def main():
    N = get_input(int)
    A = get_inputs(int)

    ans = 0
    Ai_plus_i = collections.Counter()
    for j in range(1, N+1):
        A_j = A[j-1]

        ans += Ai_plus_i[j - A_j]
        Ai_plus_i[A_j + j] += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter
N = int(input())
A = [int(hoge) for hoge in input().split()]
Plus = []
Minus = []
for n,a in enumerate(A):
    Plus.append(n + a)#i + Ai
    Minus.append(n - a)#i - Ai
CPlus = Counter(Plus)#Max2万種類
CMinus = Counter(Minus)#Max2万種類
ans = 0
for p in Plus:
    ans +=CMinus[p]
print(ans)

Submission status: Accepted

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

ans = 0
for i in range(N) :
    ans += counter[i-high[i]]
    counter[i+high[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
import sys

sys.setrecursionlimit(100000)
input = sys.stdin.readline
ACMOD = 1000000007
INF = 1 << 62


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


def llmi(n):
    return [lmi() for _ in range(n)]


N = int(input())
A = lmi()
Ay = [a - i for i, a in enumerate(A)]
Ax = [a + i for i, a in enumerate(A)]
# print(Ax,Ay)

d = collections.defaultdict(int)
ans  =0
for i in range(N):
    # check Ay
    ans += d[Ay[i]]
    # update d
    d[-Ax[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
dic1 = defaultdict(int)
dic2 = defaultdict(int)
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0

n = int(readline())
lst1 = list(map(int,readline().split()))

for idx,i in enumerate(lst1,1):
    dic1[i-idx] += 1
    dic2[i+idx] += 1

ans = 0

for i,j in dic1.items():
    ans += j*dic2[-i]

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")

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

#処理内容
def main():
	N = int(input())
	A = getlist()
	D = defaultdict(int)
	ans = 0
	for i in range(N):
		ans += D[-A[i] + i]
		D[A[i] + i] += 1

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from collections import defaultdict
import itertools
n = int(input())
lis = list(map(int,input().split()))
lis = [lis[i]-i for i in range(n)]
  #print(lis)
counter = defaultdict(int)
ans = 0
for num in lis:
    counter[num] += 1
for i,x in enumerate(lis):
    ans += counter[-x-2*i]
print(ans)

Submission status: Accepted

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

ans = 0
cnt = defaultdict(int)
for j in range(n):
    y = j - a[j]
    x = j + a[j]
    ans += cnt[y]
    cnt[x] += 1

print(ans)

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] = a[i]-i
c = Counter(b)
ans = 0
for i in range(n):
  ans += c[-a[i]-i]
  c[b[i]] -= 1
print(ans)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
A=list(map(int,input().split()))
AA=[0]*n
AAA=[0]*n
for i in range(n):
  AA[i]=i+1-A[i]
  AAA[i]=A[i]+i+1
AA.sort()
AAA.sort()
ans=0
for i in range(n):
  ans=ans+bisect.bisect_right(AA,A[i]+i+1,lo=0, hi=len(AA))-bisect.bisect_left(AA,A[i]+i+1,lo=0, hi=len(AA))
  ans=ans+bisect.bisect_right(AAA,i+1-A[i],lo=0, hi=len(AAA))-bisect.bisect_left(AAA,i+1-A[i],lo=0, hi=len(AAA))
print(ans//2)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
mod = 10**6 - 1
rec1 = {}
rec2 = {}
for i in range(n):
  tmp1 = i+1 - a[i]
  tmp2 = i+1 + a[i]
  try:
    rec1[tmp1] += 1
  except:
    rec1[tmp1] = 1
    rec2[tmp1] = 0
  try:
    rec2[tmp2] += 1
  except:
    rec2[tmp2] = 1
    rec1[tmp2] = 0
#print(rec1)
#print(rec2)
ans = 0
for x in rec1:
  ans += rec1[x] * rec2[x]
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6) #再帰関数の上限
import math
from copy import copy, deepcopy
from operator import itemgetter

from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque 
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
#dequeを使うときはpython3を使う、pypyはダメ
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone

def input(): return sys.stdin.readline()[:-1]
def printl(li): print(*li, sep="\n")
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds

#mod = 10**9+7
#w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

N = int(input())
#N, K = map(int, input().split())
#L = [int(input()) for i in range(N)]
A = list(map(int, input().split()))
#S = [list(map(int, input().split())) for i in range(N)]

Am=copy(A)
for i, a in enumerate(A):
    Am[i]=i+1-a
Am.sort()

ans=0
for i, a in enumerate(A):
    x=a+i+1
    count=bisect_right(Am,x)-bisect_left(Am,x)

    ans+=count
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

from collections import Counter

ans = 0
b = Counter()
for j in range(n):
    if j - a[j] in b:
        ans += b[j - a[j]]

    b[a[j] + j] += 1

ans = 0
c = Counter()
for i in range(n):
    if i - a[i] in c:
        ans += c[i - a[i]]

    c[a[i] + i] += 1


print(ans)

Submission status: Accepted

Solution code:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()
N=int(input())
A=list(map(int,input().split()))
c=0
lst=Counter([A[i]-(i+1) for i in range(N)])
for i in range(N):
    c+=lst[-(A[i]+i+1)]


print(c)

Submission status: Accepted

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

    npa = ct([i+1+j for i, j in enumerate(a)])
    nma = ct([i+1-j for i, j in enumerate(a)])

    cnt = 0

    for i, j in npa.items():
        cnt += j*nma[i]
    print(cnt)


main()

Submission status: Accepted

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


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    A = list(map(int, input().split()))

    tasitayatu = [0] * N
    hiitayatu = [0] * N

    for i in range(N):
        tasitayatu[i] = A[i] + i
        hiitayatu[i] = A[i] - i

    tasitacount = collections.Counter(tasitayatu)
    hiitacount = collections.Counter(hiitayatu)

    res = 0
    for i in range(N):
        res += tasitacount[-hiitayatu[i]]
        res += hiitacount[-tasitayatu[i]]

    print(res // 2)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

cnt_ind_minus_height = {}
cnt_ind_plus_height = {}
cnt_height_minus_ind = {}
cnt_minus_ind_minus_height = {}

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

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


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



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

ans = 0
    
for val in cnt_height_minus_ind:
    if val in cnt_minus_ind_minus_height:
        ans += cnt_height_minus_ind[val] * cnt_minus_ind_minus_height[val]

for val in cnt_ind_minus_height:
    if val in cnt_ind_plus_height:
        ans += cnt_ind_minus_height[val] * cnt_ind_plus_height[val]

print(ans//2)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

b = defaultdict(list)

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

ans = 0
for i in range(n):
    ans += len(b[i+a[i]])

print(ans)