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:

MOD = 10 ** 9 + 7
RLIMIT = 1000
DEBUG = 1

def main():
    for _ in inputt(1):
        n, = inputi()
        L = [0] * (n + 1)
        t = 0
        for i, p in enumerate(inputi()):
            debug(i, p)
            if i - p > 0:
                t += L[i - p]
            if i + p <= n:
                L[i + p] += 1
            debug(L, t)


        print(t)

# region M


# region import

from math import *
from heapq import *
from itertools import *
from functools import reduce, lru_cache, partial
from collections import Counter, defaultdict
import re, copy, operator, cmath
import sys, io, os, builtins
sys.setrecursionlimit(RLIMIT)

# endregion

# region fastio

BUFSIZE = 8192
class FastIO(io.IOBase):
    newlines = 0
    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = io.BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None
    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()
    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()
    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(io.IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")
def print(*args, **kwargs):
    if args:
        sys.stdout.write(str(args[0]))
        split = kwargs.pop("split", " ")
        for arg in args[1:]:
            sys.stdout.write(split)
            sys.stdout.write(str(arg))
    sys.stdout.write(kwargs.pop("end", "\n"))
def debug(*args, **kwargs):
    if DEBUG and not __debug__:
        print("debug", *args, **kwargs)
        sys.stdout.flush()
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip()
inputt = lambda t = 0: range(t) if t else range(int(input()))
inputs = lambda: input().split()
inputi = lambda k = int: map(k, inputs())
inputl = lambda t = 0, k = lambda: list(inputi()): [k() for _ in range(t)] if t else list(k())

# endregion

# region bisect

def len(a):
    if isinstance(a, range):
        return -((a.start - a.stop) // a.step)
    return builtins.len(a)
def bisect_left(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if key(a[mid]) < x: lo = mid + 1
        else: hi = mid
    return lo
def bisect_right(a, x, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    while lo < hi:
        mid = (lo + hi) // 2
        if x < key(a[mid]): hi = mid
        else: lo = mid + 1
    return lo
def insort_left(a, x, key = None, lo = 0, hi = None):
    lo = bisect_left(a, x, key, lo, hi)
    a.insert(lo, x)
def insort_right(a, x, key = None, lo = 0, hi = None):
    lo = bisect_right(a, x, key, lo, hi)
    a.insert(lo, x)
do_nothing = lambda x: x
bisect = bisect_right
insort = insort_right
def index(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    if key == None: key = do_nothing
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi and key(a[i]) == x: return a[i]
    if default != None: return default
    raise ValueError
def find_lt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_le(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo < i <= hi: return a[i - 1]
    if default != None: return default
    raise ValueError
def find_gt(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_right(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError
def find_ge(a, x, default = None, key = None, lo = 0, hi = None):
    if lo < 0: lo = 0
    if hi == None: hi = len(a)
    i = bisect_left(a, x, key, lo, hi)
    if lo <= i < hi: return a[i]
    if default != None: return default
    raise ValueError

# endregion

# region csgraph
# TODO

class Tree:
    def __init__(n):
        self._n = n
        self._conn = [[] for _ in range(n)]
        self._list = [0] * n
    def connect(a, b):
        pass

# endregion

# region ntheory

class Sieve:
    def __init__(self):
        self._n = 6
        self._list = [2, 3, 5, 7, 11, 13]
    def extend(self, n):
        if n <= self._list[-1]: return
        maxbase = int(n ** 0.5) + 1
        self.extend(maxbase)
        begin = self._list[-1] + 1
        newsieve = [i for i in range(begin, n + 1)]
        for p in self.primerange(2, maxbase):
            for i in range(-begin % p, len(newsieve), p):
                newsieve[i] = 0
        self._list.extend([x for x in newsieve if x])
    def extend_to_no(self, i):
        while len(self._list) < i: 
            self.extend(int(self._list[-1] * 1.5))
    def primerange(self, a, b):
        a = max(2, a)
        if a >= b: return
        self.extend(b)
        i = self.search(a)[1]
        maxi = len(self._list) + 1
        while i < maxi:
            p = self._list[i - 1]
            if p < b:
                yield p
                i += 1
            else: return
    def search(self, n):
        if n < 2: raise ValueError
        if n > self._list[-1]: self.extend(n)
        b = bisect(self._list, n)
        if self._list[b - 1] == n: return b, b
        else: return b, b + 1
    def __contains__(self, n):
        if n < 2: raise ValueError
        if not n % 2: return n == 2
        a, b = self.search(n)
        return a == b
    def __getitem__(self, n):
        if isinstance(n, slice):
            self.extend_to_no(n.stop + 1)
            return self._list[n.start: n.stop: n.step]
        else:
            self.extend_to_no(n + 1)
            return self._list[n]
sieve = Sieve()
def isprime(n):
    if n <= sieve._list[-1]:
        return n in sieve
    for i in sieve:
        if not n % i: return False
        if n < i * i: return True
prime = sieve.__getitem__
primerange = lambda a, b = 0: sieve.primerange(a, b) if b else sieve.primerange(2, a)
def factorint(n):
    factors = []
    for i in sieve:
        if n < i * i: break
        while not n % i:
            factors.append(i)
            n //= i
    if n != 1: factors.append(n)
    return factors
factordict = lambda n: Counter(factorint(n))

# endregion

# region main

if __name__ == "__main__":
    main()

# endregion


# endregion

Submission status: Accepted

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

ans = 0
cnt = {}
for j,a in enumerate(A[::-1]):
    j = N-1-j
    ans += cnt.get(a+j,0)
    cnt[j-a] = cnt.get(j-a,0) + 1
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
L = [0]*N
H = [0]*N
for i,a in enumerate(A):
    if 0 <= i+a < N:
        L[i+a] += 1
    if 0 <= i-a < N:
        H[i-a] += 1
ans = 0
for l,h in zip(L,H):
    ans += l*h
print(ans)

Submission status: Accepted

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

from collections import defaultdict
d = defaultdict(int)

d[a[0]] = 1
ans = 0
for i in range(1,n):
    ai = a[i]
    ans += d[ i - ai ]
    d[ ai+i ] += 1

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 + 1)
    c[i] = (i + 1) - a[i]

memo_b = {}
memo_c = {}
for i in range(n):
    if b[i] not in memo_b:
        memo_b[b[i]] = 1
    else:
        memo_b[b[i]] += 1
        
    if c[i] not in memo_c:
        memo_c[c[i]] = 1
    else:
        memo_c[c[i]] += 1

ans = 0
for num in memo_b:
    if num in memo_c:
        ans += memo_c[num] * memo_b[num]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
A = list(map(int,input().split()))
a = []
b = []
for i in range(N):
    a.append(A[i] + i)
    b.append(i - A[i])

from collections import Counter

Ac = Counter(a)
Bc = Counter(b)

ans = 0

for k in Ac.keys():
    ans += Ac[k]*Bc[k]

print(ans)

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)
for i in range(n):
	a[i]-=i
a.sort()
b.sort()
import bisect
ans=0
for i in range(n):
	ans+=bisect.bisect_right(b,a[i])-bisect.bisect_left(b,a[i])
print(ans)

Submission status: Accepted

Solution code:
import collections
n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  a[i]-=i
c=collections.Counter(a)
l=list(c.items())
d={}
for i in range(len(l)):
  d[l[i][0]]=l[i][1]
ct=0
for i in range(n):
  if -a[i]-i*2 in d:
    ct+=d[-a[i]-i*2]
print(ct)

Submission status: Accepted

Solution code:
from collections import Counter
n,*a=map(int,open(0).read().split())
one=[i+x for i,x in enumerate(a)]
two=[i-x for i,x in enumerate(a)]
def cnt(l):
	ret=sum(x*(x-1)//2 for x in Counter(l).values())
	return ret
print(cnt(one+two)-cnt(one)-cnt(two))

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


def main():
  N = int(input())
  right_count = [0] * N
  left_count = [0] * N

  for i, h in enumerate(map(int, input().split())):
    right = i + h
    left = i - h

    if right < len(right_count):
      right_count[right] += 1

    if left >= 0:
      left_count[left] += 1

  print(sum(rc * lc for rc, lc in zip(right_count, left_count)))


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,log #log2ないｙｐ
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 fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N=I()
    A=LI()
    d=defaultdict(int)
    ans = 0
    for i,a in enumerate(A):
        i+=1
        x = i-a
        ans += d[x]
        d[a+i] += 1
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

from collections import Counter
C=Counter([A[i]-i for i in range(N)])

ANS=0

for i in range(N):
    C[A[i]-i]-=1
    ANS+=C[-2*i-(A[i]-i)]

print(ANS)

Submission status: Accepted

Solution code:
MOD = 10 ** 9 + 7
INF = 10 ** 11
import sys
sys.setrecursionlimit(100000000)

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

    dic = {}
    ans = 0
    for i in range(N - 1,-1,-1):
        key = A[i] + i
        if key in dic:
            ans += dic[key]
        key2 = -A[i] + i
        if key2 in dic:
            dic[key2] += 1
        else:
            dic[key2] = 1
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
from bisect import bisect_left,bisect_right
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

def main():
    N=int(input())
    A=tuple(map(int,input().split()))
    l1=[A[i]+i+1 for i in range(N)]
    l2=[i+1-A[i] for i in range(N)]
    l1.sort()
    l2.sort()
    ans=0
    for x in l1:
        ans+=bisect_right(l2,x)-bisect_left(l2,x)
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    from collections import defaultdict

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

    i_m_Ai = defaultdict(int)
    i_p_Ai = defaultdict(int)
    for i, x in enumerate(a, start=1):
        i_m_Ai[i - x] += 1
        i_p_Ai[i + x] += 1

    ans = 0
    keys = {*i_p_Ai.keys(), *i_m_Ai.keys()}

    for key in keys:
        ans += (i_p_Ai[key] * i_m_Ai[key])
    print(ans)


if __name__ == '__main__':
    main()

# import sys
# input = sys.stdin.readline
# 
# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok

Submission status: Accepted

Solution code:
from collections import defaultdict

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

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

ans = 0

for i in range(n):
    ans += c[b[i]]

print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a_right = [i+ai for i,ai in enumerate(a,1)]
a_left  = [i-ai for i,ai in enumerate(a,1)]

a_right_count = Counter(a_right)
a_left_count  = Counter(a_left)

ans = 0
for k,v in a_right_count.items():
    ans += v * a_left_count.get(k,0)

print(ans)

Submission status: Accepted

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

num = [0] * (3*10**6)
for i in range(n):
    a[i] -= i
    if abs(a[i]) <= 10**6:
        num[a[i]] += 1

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

print(ans)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict as ddict

sys.setrecursionlimit(10**7)
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
printn = lambda x: print('\n'.join(x))

n = ni()
a = nl()
d = ddict(int)
ans = 0
for i in range(n):
    ans += d[a[i] - i]
    d[- a[i] - i] += 1
print(ans)

Submission status: Accepted

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

from collections import defaultdict
d = defaultdict(int)
res = 0
for idx,a in enumerate(A):
  if idx > 0:
    res += d[idx-a]
  d[a+idx] += 1
print (res)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

print(ans)

Submission status: Accepted

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

import sys
from collections import Counter

INF = 2**62-1

buff_readline = sys.stdin.buffer.readline
readline = sys.stdin.readline

def read_int():
    return int(buff_readline())


def read_int_n():
    return list(map(int, buff_readline().split()))

def slv(N, A):

    c = Counter()
    ans = 0
    for i, a in enumerate(A):
        ans += c[a-i]
        c[-i-a] += 1
    return ans


def main():
    N = read_int()
    A = read_int_n()
    print(slv(N, A))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

ia = {}
pair = 0
for j, a in enumerate(la):
    pair += ia.get(j - a, 0)
    ia[j + a] = ia.get(j + a, 0) + 1

print(pair)

Submission status: Accepted

Solution code:
import bisect
N = int(input())
A = list(map(int,input().split()))
left = [A[i] + i for i in range(N)]
right = [j - A[j] for j in range(N)]
right.sort()

ans = 0
for i in range(N):
	x = left[i]
	ans += bisect.bisect_right(right, x) - bisect.bisect_left(right, x)
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


def main():
    n=int(input())
    a=[int(x) for x in input().split()]
    d={}
    for i,x in enumerate(a):
        # print(i,x)
        if i-x in d:
            d[i-x]+=1
        else:
            d[i-x]=1
    ans=0

    for i,x in enumerate(a):
        d[i-x]-=1
        # print(i,x)
        if i+x in d:
            ans+=d[i+x]
    
    print(ans)

# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")

# endregion

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict
def main():
    N = int( input())
    A = list( map( int, input().split()))
    d = defaultdict( int)
    e = defaultdict( int)
    ans = 0
    for i in range(N):
        a = A[i]
        ans += d[a+(i+1)]
        ans += e[a-(i+1)]
        d[(i+1)-a] += 1
        e[-a-(i+1)] += 1
    
    print(ans)
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin, setrecursionlimit
from collections import defaultdict

setrecursionlimit(10 ** 9)


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


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

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

ans = 0
for i, a in enumerate(A, 1):
    ans += d[a - i]

print(ans)

Submission status: Accepted

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

data = [0] * N
d0 = As[0] + 1
if d0 < N:
	data[d0] = 1

count = 0
for j in range(1, N):
#	print(data)
	A = As[j]
	d = j + 1 - A
	if d >= 0:
		count += data[d]
	d = A + j + 1
	if d < N:
		data[d] += 1

print(count)

Submission status: Accepted

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

t1=[0 for i in range(200010)]
t2=[0 for i in range(200010)]

for i in range(len(a)):
  if i-a[i]>=0:
    t1[i-a[i]]+=1
  if a[i]+i<200010:
    t2[a[i]+i]+=1
ans=0
for i in range(200010):
  ans += t1[i]*t2[i]
print(ans)

Submission status: Accepted

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

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

    t = i+A[i]
    if t not in D: D[t]=0
    D[t]+=1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

d1 = defaultdict(int)
d2 = defaultdict(int)

for i in range(1, N+1):
    d1[i-A[i]] += 1
    d2[i+A[i]] += 1

ans = 0
for k in d1.keys():
    ans += d1[k]*d2[k]
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter

n = int(input())
a = list(map(int, input().split()))
b = [v-k for k,v in enumerate(a)]
c = Counter(b[1:])
now = 0
ans = 0
for i in b[:-1]:
  search = now - i
  if search in c:
    ans += c[search]
  c[i] -= 1
  now -= 2
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

n = int(input())
a = [int(item) for item in input().split()]
left_cnt = [0] * n
right_cnt = [0] * n
for i, item in enumerate(a):
    if i - item >= 0:
        right_cnt[i - item] += 1
    if i + item < n:
        left_cnt[i + item] += 1
ans = 0
for lc, rc in zip(left_cnt, right_cnt):
    ans += lc * rc
print(ans)

Submission status: Accepted

Solution code:
def Int():
    return int(input())
def Ints():
    return map(int,input().split())
def IntList():
    return list(Ints())
def IntMat(N):
    return [IntList() for i in range(N)]

N = Int()
A = IntList()

B = []

for i in range(N):
    B.append(-A[i]-(i+1))
    A[i] -= i+1
    
from collections import defaultdict

G = defaultdict(list)

for i in range(N):
    G[A[i]].append(i)
    
ans = 0
import bisect

for i in range(N):
    query = B[i]
    L = len(G[query]) - bisect.bisect(G[query],i)
    ans += L

print(ans)

Submission status: Accepted

Solution code:
import bisect
n=int(input())
a=list(map(int,input().split()))
s=[a[i]+i for i in range(n)]
di=[i-a[i] for i in range(n)]
di.sort()
ans=0
for i in range(n):
    ans+=bisect.bisect_right(di,s[i])-bisect.bisect_left(di,s[i])
print(ans)

Submission status: Accepted

Solution code:
from bisect import *
from collections import *

N = int(input())
A = list(map(int, input().split()))
C = defaultdict(int)
C[A[0]] = 1
ans = 0
for i in range(1, N):
    ans += C[i-A[i]]
    C[i+A[i]] += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
n = int(input())
a = [int(i) for i in input().split()]
l = []
r = []
for i in range(n):
   l.append(a[i]+i+1)
   r.append(i-a[i]+1)
l = Counter(l)
r = Counter(r)
ans = 0
for i in l:
   ans += l[i] * r[i]
print(ans)

Submission status: Accepted

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
from fractions import gcd
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    dic = defaultdict(int)
    n = inp()
    a = inpl()
    ans = 0
    for i in range(n):
        ans += dic[i-a[i]]
        dic[a[i]+i] += 1
    print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

B.sort()
C.sort()

num = [0] * 500000
for i in range(N):
    if B[i] < 0 or B[i] >= 500000:
         continue
    num[B[i]] += 1
ans = 0
for i in range(N):
    if C[i] < 0 or C[i] >= 500000:
         continue
    ans += num[C[i]]
print(ans)

Submission status: Accepted

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

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

d = dict()
res = 0


d[n-1-a[-1]] = 1

for i in range(n-2,-1,-1):
    if a[i]+i in d:
        res += d[a[i] + i]
    
    if i-a[i] in d:
        d[i-a[i]] += 1
    else:
        d[i-a[i]] = 1

print(res)

Submission status: Accepted

Solution code:
import os
from collections import Counter

import sys
import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


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

A = np.array(A, dtype=int)
B = (A + np.arange(1, N + 1)).tolist()
C = (A - np.arange(1, N + 1)).tolist()

c_cnt = Counter(C)
ans = 0
for k, b in Counter(B).items():
    ans += c_cnt[-k] * b
print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

first_s = [0 for _ in range(n)]
sec_s = [0 for _ in range(n)]

for i in range(n):
	sec_s[i] = a[i] - i
	# sec_s
	first_s[i] = -i - a[i]

# print("first_s", first_s)
# print("sec_s", sec_s)

seen_first_s = {}
ans = 0
for i in range(n):
	if sec_s[i] in seen_first_s:
		ans += seen_first_s[sec_s[i]]
	seen_first_s[first_s[i]] = seen_first_s.get(first_s[i], 0) + 1
print(ans)

Submission status: Accepted

Solution code:
from collections import Counter


def main():
    n = int(input())
    a = list(map(int, input().split()))
    b = []
    c = []
    for i in range(n):
        b.append(a[i] + i + 1)
        c.append(i + 1 - a[i])
    b = list(Counter(b).items())
    c = Counter(c)
    answer = 0
    for i, n in b:
        if i in c:
            answer += n * c[i]
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict


def solve(n, aaa):
    fff = aaa.copy()
    for i in range(n):
        fff[i] -= i
    ans = 0
    count = defaultdict(int)
    for i in range(n - 1, -1, -1):
        ans += count[-i - aaa[i]]
        count[fff[i]] += 1
    return ans


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))