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,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""

n = onem()

a = l()

po = [0 for i in range(5*(10**5)+1)]
if n-1-a[0] >= 0:
    po[n-1-a[0]] = 1
ans = 0
for i in range(1,n):
    ppo = n-1-i + a[i]
    if ppo > 5*(10**5):
        if n-i-1 - a[i] >= 0:
            po[n-i-1 - a[i]] += 1
        continue
    if ppo >= 0:
        ans += po[ppo]
    if n-i-1 - a[i] >= 0:
        po[n-i-1 - a[i]] += 1
print(ans)

Submission status: Accepted

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

add1 = []
sub1 = []
for i in range(n):
    add1.append(a[i] + i)
    sub1.append(i - a[i])

dict1 = {}
dict2 = {}
for i in add1:
    if i in dict1:
        dict1[i] += 1
    else:
        dict1[i] = 1
for i in sub1:
    if i in dict2:
        dict2[i] += 1
    else:
        dict2[i] = 1

sorted1 = sorted(dict1.items(), key = lambda x: x[0])
sorted2 = sorted(dict2.items(), key = lambda x: x[0])
cnt1 = 0
cnt2 = 0
ans = 0

while cnt1 < len(sorted1) and cnt2 < len(sorted2):
    if sorted1[cnt1][0] == sorted2[cnt2][0]:
        ans += sorted1[cnt1][1] * sorted2[cnt2][1]
        cnt1 += 1
        cnt2 += 1
    elif sorted1[cnt1][0] > sorted2[cnt2][0]:
        cnt2 += 1
    else:
        cnt1 += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys, bisect, math, itertools
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

n = inp()
a = inpl()
dp = defaultdict(int)
ans=0
for i in range(n):
    #check
    if i-a[i]>=0:
        ans += dp[i - a[i]]
    
    dp[i + a[i]] += 1

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# vim: set fileencoding=utf-8

# pylint: disable=unused-import, invalid-name, missing-docstring, bad-continuation


"""Module docstring
"""

import functools
import heapq
import itertools
import logging
import math
import random
import string
import sys
from argparse import ArgumentParser
from collections import defaultdict, deque
from copy import deepcopy
from typing import Dict, List, Optional, Set, Tuple


def solve(values: List[int]) -> int:
    all_values = defaultdict(int)
    for i, v in enumerate(values):
        i += 1
        all_values[i + v] += 1
    result = 0
    LOG.debug((all_values))
    for i, v in enumerate(values):
        i += 1
        result += all_values[i - v]
    return result


def do_job():
    "Do the work"
    LOG.debug("Start working")
    # first line is number of test cases
    N = int(input())
    values = list(map(int, input().split()))
    assert len(values) == N
    # values = []
    # for _ in range(N):
    #     values.append(input().split())
    result = solve(values)
    print(result)


def print_output(testcase: int, result) -> None:
    "Formats and print result"
    if result is None:
        result = "IMPOSSIBLE"
    print("Case #{}: {}".format(testcase + 1, result))
    # 6 digits float precision {:.6f} (6 is the default value)
    # print("Case #{}: {:f}".format(testcase + 1, result))


def configure_log() -> None:
    "Configure the log output"
    log_formatter = logging.Formatter("%(lineno)d - " "%(message)s")
    handler = logging.StreamHandler(sys.stdout)
    handler.setFormatter(log_formatter)
    LOG.addHandler(handler)


LOG = None
# for interactive call: do not add multiple times the handler
if not LOG:
    LOG = logging.getLogger("template")
    configure_log()


def main(argv=None):
    "Program wrapper."
    if argv is None:
        argv = sys.argv[1:]
    parser = ArgumentParser()
    parser.add_argument(
        "-v",
        "--verbose",
        dest="verbose",
        action="store_true",
        default=False,
        help="run as verbose mode",
    )
    args = parser.parse_args(argv)
    if args.verbose:
        LOG.setLevel(logging.DEBUG)
    do_job()
    return 0


if __name__ == "__main__":
    import doctest

    doctest.testmod()
    sys.exit(main())


class memoized:
    """Decorator that caches a function's return value each time it is called.
    If called later with the same arguments, the cached value is returned, and
    not re-evaluated.
    """

    def __init__(self, func):
        self.func = func
        self.cache = {}

    def __call__(self, *args):
        try:
            return self.cache[args]
        except KeyError:
            value = self.func(*args)
            self.cache[args] = value
            return value
        except TypeError:
            # uncachable -- for instance, passing a list as an argument.
            # Better to not cache than to blow up entirely.
            return self.func(*args)

    def __repr__(self):
        """Return the function's docstring."""
        return self.func.__doc__

    def __get__(self, obj, objtype):
        """Support instance methods."""
        return functools.partial(self.__call__, obj)

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_right

N = int(input())
arr = list(map(int, input().split()))
val2idx = defaultdict(list)
for j, aj in enumerate(arr):
    val2idx[j - aj].append(j)

ans = 0
for i, ai in enumerate(arr):
    if ai + i in val2idx:
        res = bisect_right(val2idx[ai + i], i)
        ans += len(val2idx[ai + i]) - res
print(ans)

Submission status: Accepted

Solution code:
import bisect
import collections
n = int(input())
a = list(map(int,input().split()))
# 1,...,n の身長はa[n-1]
# abs(i-j) == a[i]+a[j]
# a[i]+a[j]-j+i (i<=j) == 0 ????
# a[i]+i+a[j]-j == 0 ????
#とりあえず a[i]+i a[j]-j つくろう
x = [a[i]+i for i in range(n)]
y = [a[i]-i for i in range(n)]
#xに対して-yと一致するものは何こ有る？
c = collections.Counter(y)
cnt = 0
for i in range(n):
	cnt += c[-x[i]]
print(cnt)

Submission status: Accepted

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

freq=dict()
for i in range(n):
    a[i]-=i
    try:
        freq[a[i]]+=1
    except:
        freq[a[i]]=1

ans =0
for i in range(n):
    try:
        ans+=freq[-a[i]-2*i]
    except:
        pass
    freq[a[i]]-=1

print(ans)

Submission status: Accepted

Solution code:
ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n = ii()
alis = li()

for i in range(1,n):
    alis[i] -= i

from collections import defaultdict as dl
d1 = dl(int)
d2 = dl(int)
for i in range(n):
    d1[alis[i]] += 1

ans = 0
ima = 0
for i in range(n-1):
    d2[alis[i]] += 1
    tmp = -(ima + alis[i])
    ans += d1[tmp] - d2[tmp]
    ima += 2
print(ans)

Submission status: Accepted

Solution code:
if __name__ == '__main__':
    from sys import stdin
    from collections import defaultdict  # , deque
    from collections import Counter
    # import math
    # import random
    input = stdin.readline


    n = int(input())

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

    up = defaultdict(int)
    down = defaultdict(int)
    for i in range(n):
        up[i+aa[i]] += 1
        down[i-aa[i]] += 1
    
    count_up = Counter(up)
    count_down = Counter(down)

    ans = 0

    for key, value in count_up.items():
        ans += count_down[key]*value
    print(ans)

Submission status: Accepted

Solution code:
n = int(input())
l = list(map(int, input().split()))
t1 = []
t2 = []
for i in range(n):
    t1.append(l[i] + i)
    t2.append(i - l[i])
count = {}
for i in t1: count[i] = 0
for i in t2: count[i] = 0
for i in t1: count[i] -= -1
ans = 0
for i in t2:
    if i > 0:
        if count[i] != 0:
            ans += count[i]
print(ans)

Submission status: Accepted

Solution code:
import math
from functools import reduce
from collections import deque,defaultdict
import sys
sys.setrecursionlimit(10**7)

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

# スペース区切りの入力を読み込んで数値リストにして返します。
def get_nums_l():
    return [ int(s) for s in input().split(" ")]

# 改行区切りの入力をn行読み込んで数値リストにして返します。
def get_nums_n(n):
    return [ int(input()) for _ in range(n)]

# 改行またはスペース区切りの入力をすべて読み込んでイテレータを返します。
def get_all_int():
    return map(int, open(0).read().split())

def rangeI(it, l, r):
    for i, e in enumerate(it):
        if l <= i < r:
            yield e
        elif l >= r:
            break

def log(*args):
    print("DEBUG:", *args, file=sys.stderr)

INF = 999999999999999999999999
MOD = 10**9+7

n,*A = get_all_int()

X = defaultdict(int)

ans = 0
for i in range(n):
    # log(i, A[i], X[i-A[i]])
    ans += X[i-A[i]]
    X[A[i] + i] += 1

# log(X)

print(ans)

Submission status: Accepted

Solution code:
n = int(input())

arr = list(map(int, input().split()))
ar2 = [0] * n

for i in range(n):
    x = i-arr[i]
    if x >= 0:
        ar2[x] += 1

total = 0
for i in range(n):
    x = i+arr[i]
    if x < n:
        total += ar2[x]

print(total)

Submission status: Accepted

Solution code:
from collections import Counter

n=int(input())
*a,=map(int, input().split( ))
b=[a[i]-i for i in range(n)]
c =[-a[i]-i for i in range(n)]
bc=Counter(b)
cc=Counter(c)

ans=0

for k in bc:
    if k in cc:
        ans+= bc[k]*cc[k]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict


N = int(input())
A = list(map(int, input().split()))
count = defaultdict(int)
res = 0
for i, a in enumerate(A):
    if i - a in count:
        res += count[i - a]
    count[i + a] += 1
print(res)

Submission status: Accepted

Solution code:
n = int(input())
a = list(map(int,input().split()))
b = [a[i]+i+1 for i in range(n)]
c = [j+1-a[j] for j in range(n)]
b.sort()
c.sort()
b.append(float("inf"))
c.append(float("inf"))
i = 0
j = 0
count = 0
bc = 1
cc = 1
while True:
  if b[i] > c[j]:
    j += 1
  elif b[i] < c[j]:
    i += 1
  else:
    if b[i] == b[i+1]:
      bc += 1
      i += 1
    elif c[j] == c[j+1]:
      cc += 1
      j += 1
    else:
      count += bc*cc
      bc = 1
      cc = 1
      i += 1
      j += 1
  if i >= n and j >= n:
    break
  if i == n+1:
    i = n
  if j == n+1:
    j = n
print(count)

Submission status: Accepted

Solution code:
from collections import defaultdict
import collections
N = int(input())
a = list(map(int,(input().split())))
b = list(range(N))
wa = [0]*N
sa = [0]*N
for i in range(N):
    wa[i] = a[i]+b[i]
    sa[i] = b[i]-a[i]

cw = collections.Counter(wa)
cs = collections.Counter(sa)
dw = defaultdict(lambda:0)
ds = defaultdict(lambda:0)

for k in cw:
    dw[k] = cw[k] 
for k in cs:
    ds[k] = cs[k] 

mash = []
for i in range(N):
    mash.append(wa[i])
    mash.append(sa[i])
mash = set(mash)

ans = 0
for num in mash:
    ans += dw[num]*ds[num]

print(ans)

Submission status: Accepted

Solution code:
import collections
n = int(input())
a = list(map(int, input().split()))
x = []
for i in range(n):
    x.append(a[i]-i)
y = []
for j in range(n):
    y.append(-(a[j]+j))
    
X = collections.Counter(x)
Y = collections.Counter(y)



ans = 0
z = X.keys()
#print(z)
for i in z:
    p =X.get(i,0)
    q =Y.get(i,0)
    ans += p*q
print(ans)

Submission status: Accepted

Solution code:
import bisect,sys
import math
from collections import deque

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


def ssRaw():
    return input().split()


def isRaw():
    return list(map(int, ssRaw()))

INF = 1 << 29

DIV = (10**9) + 7

def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac =fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV
        
    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s+=a
        yield s


sys.setrecursionlimit(200005)


def main():
    N = iRaw()
    As = isRaw()
    ais = [(Aa+a,a) for a,Aa in enumerate(As)]
    ais.sort()
    ais0 = [ai[0] for ai in ais]
    ans = 0
    for b,Ab in enumerate(As):
        num = b-As[b]
        l = bisect.bisect_left(ais0, num)
        r = bisect.bisect_right(ais0, num)
        ans+=max(r-l,0)
    return ans

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import Counter


n = int(input())
an = list(map(int, input().split(' ')))

nn = list(range(1, n + 1))

nam = [None] * n
for i in range(n):
    nam[i] = nn[i] - an[i]
    
nap = [None] * n
for i in range(n):
    nap[i] = nn[i] + an[i]
    
c = Counter()
for p in nap:
    c[p] += 1

ans = 0
for m in nam:
    ans += c[m]

print(ans)

Submission status: Accepted

Solution code:
n,*x = map(int,open(0).read().split())
ans = 0
xr = {}
xl = {}
for i in range(n):
  xrt = i+x[i]
  if xrt < n:
    if xrt in xr:
      xr[xrt] += 1
    else:
      xr[xrt] = 1
  xlt = i-x[i]
  if xlt >= 0:
    if xlt in xl:
      xl[xlt] += 1
    else:
      xl[xlt] = 1
for i in xr.keys():
  if i in xl:
    ans += xr[i]*xl[i]
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+1
    a[i]=i+1-a[i]
A=Counter(a)
B=Counter(b)
ans=0
for i in A:
    if i in B:
        ans+=A[i]*B[i]
print(ans)

Submission status: Accepted

Solution code:
n =int(input())

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

d = [[0,0] for i in range(n)]

for i in range(n):
  if i-ls[i]>=0:
    d[i-ls[i]][1]+=1
  if i+ls[i]<n:
    d[i+ls[i]][0]+=1

ans = 0
for a,b in d:
  ans += a*b
print(ans)

Submission status: Accepted

Solution code:
N = int(input())
right_count = [0 for i in range(N)]
left_count = [0 for i in range(N)]
A = list(map(int, input().split()))

for i, a in enumerate(A):
    if i - a >= 0:
        left_count[i - a] += 1
    if i + a < N:
        right_count[i + a] += 1

answer = 0
for i in range(N):
    answer += left_count[i] * right_count[i]

print(answer)

Submission status: Accepted

Solution code:
import sys
import math  # noqa
import bisect  # noqa
import queue  # noqa


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


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

    B = A.copy()
    for i in range(N):
        B[i] += (i + 1)

    cnt = {}
    for b in B:
        if b not in cnt:
            cnt[b] = 1
        else:
            cnt[b] += 1

    res = 0
    for i in range(N - 1, -1, -1):
        r = (i + 1) - A[i]
        if r in cnt:
            res += cnt[r]

    print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict
def input(): return sys.stdin.readline().strip()


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

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

    ans = 0
    for val in d1:
        ans += d1[val] * d2[val]
    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

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

from collections import defaultdict

cnt = defaultdict(int)

for j, a in enumerate(A, 1):
    if j == 1: continue
    cnt[j - a] += 1

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

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

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

ans = 0
counts = Counter()
for i, h in enumerate(A):
    ans += counts[i - h]
    counts[h + i] += 1
print(ans)

Submission status: Accepted

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

ai = []
d = {}
for i, item in enumerate(a):
    ai.append(i + item)
    aj = i - item
    if aj in d:
        d[aj].append(i)
    else:
        d[aj] = [i]
ans = 0
for i, aii in enumerate(ai):
    if aii in d:
        index = bisect.bisect_right(d[aii], i)
        ans += len(d[aii]) - index


print(ans)

Submission status: Accepted

Solution code:
import bisect
import copy
import heapq
import sys
import itertools
import math
import queue
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]
def init_dp1(init, N): return [init for _ in range(N)]
def init_dp2(init, N, M): return [[init for _ in range(M)] for _ in range(N)]


class V:
    def __init__(self, f, v=None):
        self.f = f
        self.v = v
 
    def __str__(self):
        return str(self.v)
 
    def ud(self, n):
        if n is None:
            return

        if self.v is None:
            self.v = n
            return
        self.v = self.f(self.v, n) 


def main():
    N = int(input())
    A = read_list()

    S = [A[0] + A[i] - i for i in range(1, N)]
    D = {}
    for s in S:
        D[s] = D.setdefault(s, 0) + 1

    res = 0
    t = 0
    for i in range(N - 1):
        res += D.setdefault(t, 0)
        D[S[i]] -= 1
        t -= A[i + 1] - A[i] + 1
    
    print(res)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
N=int(input())
A=list(map(int,input().split(' ')))
A_sort = sorted([A[i]-i for i in range(N)])
ans = 0
for n,i in enumerate(A):
    ans += bisect.bisect_right(A_sort,-(n+i))-bisect.bisect_left(A_sort,-(n+i))
print(ans)

Submission status: Accepted

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

def main():

    N = int(input())
    a = list(map(int,input().split()))
    pl = {}
    ans = 0
    for i,num in enumerate(a):
        s = num+i
        t = num-i
        if -t in pl:
            ans += pl[-t]
        if s not in pl:
            pl[s] = 1
        else:
            pl[s] += 1

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

Submission status: Accepted

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

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

cntB = Counter(B)
cntC = Counter(C)

ans = 0
for k,v in cntB.items():
    ans += v * cntC[-k]
print(ans)

Submission status: Accepted

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

# Ai - i == -Aj - j
l = [A[i - 1] - i  for i in range(1, N + 1)]
r = [-A[j - 1] - j  for j in range(1, N + 1)]

cnt_l = {}
for item in l:
    key = str(item)
    cnt_l.setdefault(key, 0)
    cnt_l[key] += 1
    
cnt_r = {}
for item in r:
    key = str(item)
    cnt_r.setdefault(key, 0)
    cnt_r[key] += 1

ans = 0
for key, val in cnt_l.items():
    cnt_r.setdefault(key, 0)
    ans += val * cnt_r[key]

print(ans)

Submission status: Accepted

Solution code:
N = int(input())
a = list(map(int,input().split()))
s = {}
w = {}
for i in range(N):
	if i+1-a[i] < 2:
		pass
	elif i+1-a[i] in s:
		s[i+1-a[i]] += 1
	else:
		s[i+1-a[i]] = 1
	if i+1+a[i] >= N:
		pass
	elif i+1+a[i] in w:
		w[i+1+a[i]] += 1
	else:
		w[i+1+a[i]] = 1
ans = 0
for key, value in s.items():
	if key in w:
		ans += value*(w[key])
print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())
A = [0]
A.extend([int(i) for i in input().split()])
d1 = {}
d2 = {}
for i in range(1, n+1):
	u = A[i] + i
	v = A[i] - i
	d1[u] = d1.get(u,0)+1
	d2[v] = d2.get(v,0)+1

# ~ print(d1)
# ~ print(d2)
	
ans = 0

for e in d1:
	ans += d1[e] * d2.get(-e,0)
	
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
#from collections import defaultdict
#d = defaultdict(int)
#import fractions
#import math
#import collections
#from collections import deque
#from bisect import bisect_left
#from bisect import insort_left
#N = int(input())
#A = list(map(int,input().split()))
#S = list(input())
#S.remove("\n")
#N,M = map(int,input().split())
#S,T = map(str,input().split())
#A = [int(input()) for _ in range(N)]
#S = [input() for _ in range(N)]
#A = [list(map(int,input().split())) for _ in range(N)]
#import itertools
#import heapq
#import numpy as np
#INF = float("inf")
N = int(input())
A = list(map(int,input().split()))
li = [[] for _ in range(N)]
for i in range(N):
    a = A[i]
    if i-a>0:
        li[i-a].append(i)
    if i+a<N:
        li[i+a].append(i)
s = 0
for j in range(N):
    q = li[j]
    n = len(q)
    if n < 2:
        continue
    smal = 0
    big = 0
    for k in q:
        if k < j:
            smal += 1
        else:
            big += 1
    s += smal*big
print(s)

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N=int(input())
    *A,=map(int, input().split())

    B=[i-A[i] for i in range(N)]
    C=[i+A[i] for i in range(N)]
    from collections import Counter
    b=Counter(B)
    c=Counter(C)
    ans=0
    for k,v in b.items():
        ans+=v*c[k]
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
input()
counts = {}
ans = 0
for i, h in enumerate(map(int, input().split())):
    i += 1
    ans += counts.get(i - h, 0)
    counts[i + h] = counts.get(i + h, 0) + 1
print(ans)

Submission status: Accepted

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

L1 = [0]*N
L2 = [0]*N
for i in range(N):
    L1[i] = i+1-A[i]
    L2[i] = i+1+A[i]

L1.sort()
L2.sort()

import bisect

ans = 0
for l in L1:
    a = bisect.bisect_right(L2, l)
    b = bisect.bisect_left(L2, l)
    ans += a-b

print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return map(int,input().split())
def LI(): return list(map(int,input().split()))

def main():
    N = INT()
    A = LI()

    minus = [0]*N
    plus = [0]*N

    for i in range(N):
        minus[i] = i+1-A[i]
        plus[i] = i+1+A[i]
    from collections import defaultdict
    count = defaultdict(int)

    plus_pointer = 0
    minus_pointer = 1
    answer = 0
    while minus_pointer < N:
        count[plus[plus_pointer]] += 1
        answer += count[minus[minus_pointer]]
        plus_pointer += 1
        minus_pointer += 1
    
    print(answer)
    return
if __name__ == '__main__':
    main()

Submission status: Accepted

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

    API = dict()
    ans = 0
    for i,a in enumerate(A):
        api = a+i+1
        ami = i+1-a

        if ami in API:
            ans += API[ami]

        if not api in API:
            API[api]=0
        API[api]+=1
        
    print(ans)




if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

b = [a[i] + i + 1 for i in range(n)]
memo = {}
memo[b[0]] = 1

ans = 0
for i in range(1, n):
  if 2 * i + 2 - b[i] in memo:
    ans += memo[2 * i + 2 - b[i]]
  
  if b[i] in memo:
    memo[b[i]] += 1
  else:
    memo[b[i]] = 1

print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

dic = defaultdict(int)

for i in range(N):
    dic[(i + 1) - A[i]] += 1

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

print (ans)

Submission status: Accepted

Solution code:
import bisect

n=int(input())
alist = list(map(int, input().split()))
walist=[]
salist=[]
for i in range(n):
    walist.append(alist[i]+i+1)
    if i!=0:
        salist.append(i+1-alist[i])

#print(walist,len(walist))
#print(salist,len(salist))

salist=sorted(salist)
salist2=[]
salist3=[]
mae=0.5
for sl in salist:
    if sl==mae:
        salist2[-1][1]+=1
    else:
        salist2.append([sl, 1])
        salist3.append(sl)
    mae=sl

#print(salist2)
#print(salist3)

answer=0

for i in range(n-1):
    basho=bisect.bisect_left(salist3, walist[i])
    if basho<len(salist3):
        #print(basho, walist[i], salist3[basho])
        if walist[i]==salist3[basho]:
            #print("!")
            answer+=salist2[basho][1]
    #print(salist[i+1])
    if i!=n-2:
        basho=bisect.bisect_left(salist3, salist[i])
        salist2[basho][1]-=1
    #print(salist2, answer)

print(answer)

Submission status: Accepted

Solution code:
N=int(input())
L=[0]+list(map(int,input().split()))
for i in range(len(L)):
    L[i]-=i

D={}
for i in range(1,len(L)):
    if L[i] not in D:
        D[L[i]]=1
    else:
        D[L[i]]+=1

ans=0
for i in range(1,len(L)):
    if -2*i-L[i] in D:
        ans+=D[-2*i-L[i]]
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

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

ans = 0
X = defaultdict(int)
for i in range(1, N):
    X[i + A[i - 1]] += 1
    ans += X[i + 1 - A[i]]
print(ans)

Submission status: Accepted

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

from collections import defaultdict
lis1=defaultdict(int)
lis2=defaultdict(int)
for i in range(1,n+1):
    lis1[-a[i-1]-i] += 1
    lis2[i-a[i-1]] += 1

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

print(ans//2)

Submission status: Accepted

Solution code:
n=int(input())
l=list(map(int,input().split()))
a={}
b={}
count=0
for i in range(n):
	t=l[i]-(i+1)
	if t in a:
		a[t]+=1
	else:
		a[t]=1
	t=-l[i]-(i+1)
	if t in b:
		b[t]+=1
	else:
		b[t]=1
		# b[t].add(i+1)
for i in a:
	if i in b:
		count+=a[i]*b[i]
print(count)

Submission status: Accepted

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

L=[]
R=[]
for i in range(N):
    l=A[i]+i
    r=i-A[i]
    L.append(l)
    R.append(r)

x=dict()
y=dict()
for i in range(N):
    val=R[i]
    if val in x:
        x[val]+=1
    else:
        x[val]=1

ans=0
for i in range(N):
    val=L[i]
    if val in x:
        ans+=x[val]

print(ans)

Submission status: Accepted

Solution code:
N=int(input())
A = [int(i) for i in input().split()]
left = [0] * N
right = [0] * N
for i,a in enumerate(A):
    if 0 <= i-a:
        left[i - a] += 1
    if i + a < N:
        right[i + a] += 1
ans = 0
for i in range(N):
    ans += left[i] * right[i]
print(ans)

Submission status: Accepted

Solution code:
n,*a=map(int,open(0).read().split())

# mx=n*(n-1)//2
# n <=2*10**5
from collections import Counter
b=[]
c=[]
for i,q in enumerate(a):
    b.append(i+q)
    c.append(i-q)
# print(b,c)
bb=Counter(b).items()
cc=Counter(c)

# print(bb,cc)
ans=0
for (bi,bj) in bb:
    ans+=bj*cc[bi]
print(ans)