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: Time Limit Exceeded

Solution code:
import itertools

input_line = int(input())

input_list = input().split()

for i in range(input_line):
  input_list[i] = int(input_list[i])

combination_list = list(itertools.combinations(input_list,2))
combination_num = list(itertools.combinations(range(1,input_line+1),2))
count = 0
for i in range(len(combination_list)):
    if(sum(combination_list[i]) == abs (combination_num[i][0]- combination_num[i][1])):
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
num_participants = int(input(' '))

heights = [int(h) for h in input().split(' ')]

num_valid_pairs = 0

diff_in_idx = num_participants - 1
min_sum_of_height = 2 * min(heights)

while (diff_in_idx >= min_sum_of_height):
  for idx in range(num_participants - diff_in_idx):
    if abs(heights[idx] + heights[idx+diff_in_idx]) == diff_in_idx:
      num_valid_pairs += 1
  diff_in_idx -= 1
      
print(num_valid_pairs)

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

tmp = list(map(lambda x: x[0] + 1 + x[1], enumerate(seq)))
tmp2 = list(map(lambda x: (x[0] + 1) - x[1], enumerate(seq)))

l = len(list(filter(lambda x: x[0] == x[1], list(itertools.product(tmp, tmp2)))))
print(l)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import bisect


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    negA = []
    idx_negA = []
    for i, a in enumerate(A):
        negA.append(i - a)
        idx_negA.append(i)

    negA = sorted(negA)
    ans = 0
    for i in range(N):
        searched_idx = bisect.bisect_left(negA, i + A[i])

        if searched_idx == N:
            continue
        else:
            if idx_negA[searched_idx] > i:
                while negA[searched_idx] == i + A[i] and searched_idx <= N - 1:
                    ans += 1
                    if searched_idx == N - 1:
                        break
                    searched_idx += 1

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import itertools

input_line = int(input())

input_list = input().split()
combination_list = []
for i in range(input_line):
  input_list[i] = int(input_list[i])

for i in itertools.combinations(input_list,2):
    combination_list.append(i)

combination_num = list(itertools.combinations(range(1,input_line+1),2))
count = 0
for i in range(len(combination_list)):
    if(sum(combination_list[i]) == abs (combination_num[i][0]- combination_num[i][1])):
        count += 1

print(count)

Submission status: Time Limit Exceeded

Solution code:
num_participants = int(input(' '))

heights = [int(h) for h in input().split(' ')]

num_valid_pairs = 0

diff_in_idx = num_participants - 1
while (diff_in_idx >= 2):
  for idx in range(num_participants - diff_in_idx):
    if abs(heights[idx] + heights[idx+diff_in_idx]) == diff_in_idx:
      num_valid_pairs += 1
  diff_in_idx -= 1
      
print(num_valid_pairs)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

c = 0
for i in range(N-1):
    for j in range(i+A[i], N):
        if abs(i-j) == A[i] + A[j]:
            c += 1
            
print(c)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

c = 0
for i in range(N-1):
    for j in range(i+1, N):
        if abs(i-j) == A[i] + A[j]:
            c += 1
            
print(c)

Submission status: Time Limit Exceeded

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools, copy
from math import *
from bisect import *
from heapq import *
from collections import *


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

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N = In.int()
A = In.ints()
drueb = [defaultdict(int) for i in range(N)]

for i in range(N):
    if i>=1:
        drueb[i] = copy.deepcopy(drueb[i-1])
    val = i+1
    drueb[i][A[i]-val] += 1

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

    if j<len(drueb):
        if -A[i]-(i+1) in drueb[-1]:
            ans+=drueb[-1][-A[i]-(i+1)]
    
Out.int(ans)
        
######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

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

ans = 0
for i in range(1, n+1):
    for j in range(2, n + 1):
        if i + a[i-1] == j - a[j-1]: ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

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

count = 0
for i in range(N-1):
    for j in range(i+1, N):
        if abs(i-j) == A[i] + A[j]:
            count += 1
            
print(count)

Submission status: Time Limit Exceeded

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

ans=0
for i in range(n):
    for j in range(i-1,n):
        if i+x[i]==j-x[j]:
            ans+=1
print(ans)

Submission status: Time Limit Exceeded

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

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

    cnt = 0

    for i in range(n-1):
        b = a[i]
        c = 0
        for j in range(i+b, n):
            if a[j] == c:
                cnt += 1
            c += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools
N = int(input())
A = input().split()
Ai = [int(s) for s in A]
count = 0
for x, y in itertools.combinations(range(N), 2):
        if abs(x-y) == Ai[x]+Ai[y]:
            count += 1
print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def resolve():
    n=int(input())
    a = list(map(int, input().split()))
    b=[0]*n
    c=[0]*n
    ans=0
    for i in range(n):
        b[i]=a[i]+i
    for i in range(n):
        c[i]=i-a[i]
    bc=set(b).intersection(set(c))
    bd={}
    cd={}
    for i in bc:
        bd[i]=0
        for j in b:
            if j==i:
                bd[i]+=1
    for i in bc:
        cd[i]=0
        for j in c:
            if j ==i:
                cd[i]+=1
    ansb=list(bd.values())
    ansc=list(cd.values())
    for k in range(len(bc)):
        ans+=ansb[k]*ansc[k]
    print(ans)
resolve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input()) #1行目のNを取得する
S = list(range(1,N+1))
A = list(map(int, input().split()))
K = 0
D =dict(zip(S,A))
for i in range(1,N+1):
  for m in range(1,N+1):
    if abs(i-m) == D[i]+D[m]:
      K = K + 1
      
print(int(K/2))

Submission status: Time Limit Exceeded

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

height_minus_index_list = []
height_plus_index_list = []
height_plus_index_inverse_list = []

for i in range(n):
    height_minus_index_list.append(a_list[i] - (i + 1))
    height_plus_index_list.append(a_list[i] + (i + 1))
    height_plus_index_inverse_list.append(-1 * (a_list[i] + (i + 1)))

match_count = 0
for i in range(n):
    for k in range(i+1, n):
        if k - i == a_list[i] + a_list[k]:
            match_count += 1
        # if height_minus_index_list[i] == height_plus_index_list[k] or height_plus_index_inverse_list[i] == height_minus_index_list[k]:
            # match_count += 1

print(match_count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.array(input().split(), np.int32)
S = np.array([A[i] - i for i in range(N)])
T = np.array([-A[i] - i for i in range(N)])
# j > i
# S[j] == T[i]
ans = 0
for j in range(N):
    for i in range(j - 1, -1, -1):
        if S[j] == T[i]:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import time
startTimeProblem=time.time()

import fileinput, sys, itertools, functools
from math import *
from bisect import *
from heapq import *
from collections import *

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

class InputHelper:
    def __init__(self):
        self.myinput = fileinput.input()

    def isLocal(self):
        return not fileinput.isstdin()

    def int(self):
        return int(self.myinput.readline().rstrip())

    def ints(self):
        return [int(_) for _ in self.myinput.readline().rstrip().split()]

    def str(self):
        return self.myinput.readline().rstrip()

    def strs(self):
        return [_ for _ in self.myinput.readline().rstrip().split()]

class OutputHelper:
    def int(self, a):
        print(a)    

    def ints(self, a):  
        print(" ".join([str(_) for _ in a]))
    
    def intsNL(self, a):
        for _ in a:
            print(_)
    
    def str(self, s):
        print(s)

    def strs(self, s):
        print(" ".join([_ for _ in s]))

    def strsNL(self, s):
        for st in s:
            print(st)

class ListNode:
    def __init__(self, val):
        self.val = val
        self.next = None
        self.prev = None

In = InputHelper()
Out = OutputHelper()

######################################

N = In.int()
A = In.ints()

ans=0
for i in range(N):
    for j in range(i+A[i]+1,N):
        if A[i]+A[j]==j-i:
            ans+=1
    
Out.int(ans)
        
######################################

if len(sys.argv)>2 and sys.argv[2]=="TIMEIT":
    fin = (time.time()-startTimeProblem)*1000
    print("{:.2f}".format(fin) + "ms")

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
A = [int(i) for i in input().split()]
S = [A[i] - i for i in range(N)]
T = [-A[i] - i for i in range(N)]
# j > i
# S[j] == T[i]
ans = 0
for j in range(N):
    for i in range(j - 1, -1, -1):
        if S[j] == T[i]:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))

    L = [i+a for i, a in enumerate(A)]
    R = [i-a for i, a in enumerate(A)]
    #print(L)
    #print(R)

    #はじめL_t = defaultdict(list)としてiの候補を追加していったが、iとjは重複しないのでチェックが不要
    '''
    L_t = defaultdict(int)
    for i, l in enumerate(L):
        L_t[l] += 1
    R_t = defaultdict(int)
    for j, r in enumerate(R):
        R_t[r] += 1
    '''
    L_t = Counter(L)
    R_t = Counter(R)
    x_max = max(L)
    x_min = min(R)
    cnt = 0
    for x in range(x_min, x_max+1):
        l_candidate = L_t[x]
        r_candidate = R_t[x]

        cnt += l_candidate * r_candidate

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
#from functools import lru_cache
import itertools

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    '''
    L = []
    R = []
    for i, a in enumerate(A):
        L.append(i+a)
        R.append(i-a)
    '''
    L = [i+a for i, a in enumerate(A)]
    R = [i-a for i, a in enumerate(A)]
    #print(L)
    #print(R)

    #はじめdefaultdict(list)としてiの候補を追加していったが、iとjは重複しないのでチェックが不要
    L_t = defaultdict(int)
    for i, l in enumerate(L):
        L_t[l] += 1
    R_t = defaultdict(int)
    for j, r in enumerate(R):
        R_t[r] += 1

    x_max = max(L)
    x_min = min(R)
    cnt = 0
    for x in range(x_min, x_max+1):
        l_candidate = L_t[x]
        r_candidate = R_t[x]

        cnt += l_candidate * r_candidate

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools

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

for p in itertools.combinations(range(1, n+1), 2):
    if abs(p[0] - p[1]) == a[p[0]-1] + a[p[1]-1]: ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N = int(input())
A = list(enumerate(list(map(int, input().split()))))
count = 0
B = sorted(A,key=lambda x:x[1])
h = [x[1] for x in B]
for i in range(2,N):
    if h[0] + h[1] > i:
        continue
    elif h[-1] + h[-2] < i:
        break
    else:
        for j in range(N-1):
            c = h[j]
            if c >= i:
                break
            else:
                d = i - c
                bs = bisect.bisect_left(h,d)
                if bs < N:
                    if bs <= j:
                        bs = j + 1
                    for k in range(bs,N):
                        if h[k] == d:
                            if abs(B[j][0]-B[k][0]) == i:
                                count += 1
                        else:
                            break
print(count)

Submission status: Time Limit Exceeded

Solution code:
n=int(input());a=map(int,input().split());b,c,f=[],[],0
for i,q in enumerate(a):b+=i+q,;c+=i-q,
from collections import*
for d,e in Counter(b).items():f+=e*Counter(c)[d]
print(f)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from operator import itemgetter


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    _ = sys.stdin.readline()
    a = list(_ia())
    l = {}
    r = {}
    for i, ai in enumerate(a):
        li = ai + i + 1
        ri = i + 1 - ai
        l[li] = l.get(li, 0) + 1
        r[ri] = r.get(ri, 0) + 1
    ra = list(r.keys())
    ra.sort()
    n = len(ra)

    li = 0
    ans = 0
    for kl, vl in sorted(l.items(), key=itemgetter(0)):
        li += bisect.bisect_left(ra[li:], kl)
        if li >= n:
            break
        kr = ra[li]
        if kl == kr:
            ans += vl * r[kr]
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
n=input()
l=list(map(int,input().split()))
x=0
c=list()
for i in range(1,len(l)+1):
  a=i+l[i-1]
  c.append(a)
  b=i-l[i-1]
  if b in c:
    x=x+c.count(b)
print(x)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
#from functools import lru_cache
import itertools

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    '''
    L = []
    R = []
    for i, a in enumerate(A):
        L.append(i+a)
        R.append(i-a)
    '''
    L = [i+a for i, a in enumerate(A)]
    R = [i-a for i, a in enumerate(A)]
    #print(L)
    #print(R)
    L_t = defaultdict(list)
    for i, l in enumerate(L):
        L_t[l].append(i)
    R_t = defaultdict(list)
    for j, r in enumerate(R):
        R_t[r].append(j)

    x_max = max(L)
    x_min = min(R)
    cnt = 0
    for x in range(x_min, x_max+1):
        l_candidate = L_t[x]
        r_candidate = R_t[x]
        if len(l_candidate) == 0 or len(r_candidate) == 0:
            continue
        else:
            cnt += len(l_candidate) * len(r_candidate)
            #answer_set = set()
            #print(x)
            #print(l_candidate)
            #print(r_candidate)
            #for i,j in itertools.product(l_candidate, r_candidate):
            #    answer_set.add((i,j))
            #cnt += len(answer_set)

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

n= int(input())
l=[0]+list(map(int,input().split()))

d=[0]*(n+1)
for i in range(1,n+1):
    for k in range(i+1,n+1):
        if k-i==l[k]+l[i]:
            d[k-i]+=1
print(sum(d))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
#from functools import lru_cache
import itertools

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    L = []
    R = []
    for i, a in enumerate(A):
        L.append(i+a)
        R.append(i-a)
    #print(L)
    #print(R)
    L_t = defaultdict(list)
    for i, l in enumerate(L):
        L_t[l].append(i)
    R_t = defaultdict(list)
    for j, r in enumerate(R):
        R_t[r].append(j)

    x_max = max(L)
    x_min = min(R)
    cnt = 0
    for x in range(x_min, x_max+1):
        l_candidate = L_t[x]
        r_candidate = R_t[x]
        if len(l_candidate) == 0 or len(r_candidate) == 0:
            continue
        else:
            cnt += len(l_candidate) * len(r_candidate)
            #answer_set = set()
            #print(x)
            #print(l_candidate)
            #print(r_candidate)
            #for i,j in itertools.product(l_candidate, r_candidate):
            #    answer_set.add((i,j))
            #cnt += len(answer_set)

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(N):
  l.append(i-A[i])

ans = 0
for i in range(N):
  ans += l.count(i+A[i])
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(N-1):
    for j in range(i+1):
        if A[j]+A[j+(N-i-1)] == N-i-1:
            count += 1

print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
#from functools import lru_cache
import itertools

def main():
    N = int(input())
    A = tuple(int(c) for c in input().split(' '))
    L = []
    R = []
    for i, a in enumerate(A):
        L.append(i+a)
        R.append(i-a)
    #print(L)
    #print(R)
    L_t = defaultdict(list)
    for i, l in enumerate(L):
        L_t[l].append(i)
    R_t = defaultdict(list)
    for j, r in enumerate(R):
        R_t[r].append(j)

    x_max = max(L)
    x_min = min(R)
    cnt = 0
    for x in range(x_min, x_max+1):
        l_candidate = L_t[x]
        r_candidate = R_t[x]
        if len(l_candidate) == 0 or len(r_candidate) == 0:
            continue
        else:
            answer_set = set()
            for i,j in itertools.product(l_candidate, r_candidate):
                answer_set.add((i,j))
            cnt += len(answer_set)

    print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from collections import defaultdict
ar = defaultdict(list)
al = defaultdict(list)

for i in range(n):
    al[i+a[i]].append(i)
    ar[i-a[i]].append(i)

mi = 0-max(a)
ma = n+max(a)

ans = 0
for i in range(mi,ma):
    ans += len(ar[i]) * len(al[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

from collections import defaultdict
ar = defaultdict(list)
al = defaultdict(list)

for i in range(n):
    al[i+a[i]].append(i)
    ar[i-a[i]].append(i)

mi = 0-max(a)
ma = n+max(a)

ans = 0
for i in range(mi,ma):
    ans += len(ar[i]) * len(al[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/bin/bash
''':'
docker run --rm -it -v $(cd $(dirname $0) && pwd):/vo:ro pypy:3-2.4.0 \
   /bin/bash -c "pypy3 /vo/$(basename $0) < /vo/input.txt"
exit $?
'''
import sys
import bisect
from operator import itemgetter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    a = list(_ia())
    l = {}
    for i, ai in enumerate(a):
        aip = ai + i + 1
        l[aip] = l.get(aip, 0) + 1

    r = list(i+1-ai for i, ai in enumerate(a))
    r.sort()
    li = 0
    ans = 0
    for k in sorted(l.keys()):
        r = r[li:]
        li = bisect.bisect_right(r, k)
        ans += l[k] * (li - bisect.bisect_left(r[:li], k))
        if li >= n:
            break
    return ans


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

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
from operator import itemgetter


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def main():
    n = _i()
    a = list(_ia())
    l = {}
    for i, ai in enumerate(a):
        aip = ai + i + 1
        l[aip] = l.get(aip, 0) + 1

    r = list(i+1-ai for i, ai in enumerate(a))
    r.sort()
    li = 0
    ans = 0
    for k, v in sorted(l.items(), key=itemgetter(0)):
        r = r[li:]
        li = bisect.bisect_right(r, k)
        ans += v * (li - bisect.bisect_left(r[:li], k))
        if li >= n:
            break
    return ans


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

Submission status: Time Limit Exceeded

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

wa = []

for i in range(n) :
    wa.append(i+1+a[i])
    ans += wa.count(i+1-a[i])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

nums = np.arange(1,int(input())+1)
A = np.array(list(map(int, input().split())))

L = nums + A
R = nums - A

from collections import defaultdict
dL = defaultdict(list)
dR = defaultdict(list)

Xmax = max(max(L), max(R))
Xmin = min(min(L), min(R))

for i in nums:
  dL[L[i-1]].append(i-1)
  dR[R[i-1]].append(i-1)
  
cnt = 0
for x in range(Xmin, Xmax+1):
  i_list = dL[x]
  j_list = dR[x]
  for i in i_list:
    for j in j_list:
      if j>i:
        cnt+=1
print(cnt)

Submission status: Time Limit Exceeded

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

agents = {}
n_pair = 0

for i, a in enumerate(a_list):
  x = i - a
  if x not in agents:
    agents[x] = []
  agents[x].append(i)

for i, a in enumerate(a_list):
  x = i + a
  if x in agents:
    for j in agents[x]:
      if i != j:
        n_pair += 1
print(n_pair)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

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

sum = 0
for i in range(n-1):
    sum += q[i+1:].count(p[i])

print(sum)

Submission status: Time Limit Exceeded

Solution code:

N = int(input())

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

plus = []
minus = []

for i, j in enumerate(A):
    plus.append(i+j)
    minus.append(i-j)

for i in plus:
    for j in minus:
        if i == j:
            ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

ans = 0
for i in range(n):
    x = a[i]
    if x >= n-i:
        continue
    else:
        for j in range(i+x+1,n):
            if a[j]+x == j-i:
                ans += 1
print(ans)

Submission status: Time Limit Exceeded

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

B=[i+A[i] for i in range(N)]
C=[i-A[i] for i in range(N)]

B.sort(reverse=True)
C.sort(reverse=True)

ans=0

while(len(B)>0 and len(B)>0):
  if B[0]>C[0]:
    del B[0]
  elif B[0]<C[0]:
    del C[0]
  else:
    i=1
    j=1
    while i<len(B) and B[i]==B[0]:
      i+=1
    while j<len(C) and C[j]==C[0]:
      j+=1
    ans+=i*j
    del B[0:i]
    del C[0:j]

print(ans)

Submission status: Time Limit Exceeded

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

xlist=[]
ylist=[]
checklist=[]

for i,a in enumerate(alist):
    xlist.append((i+1)+a)
    ylist.append((i+1)-a)
    if ((i+1)-a)>0:
        checklist.append((i+1)-a)

checklist=set(checklist)
output=0
for check in checklist:
    output+= xlist.count(check)*ylist.count(check)

print(output)

Submission status: Time Limit Exceeded

Solution code:
import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))
n = int(sys.stdin.readline())
a = inpl()
count = 0
maxx = max(a)
minn = min(a)
for i in range(n):
    for j in range(i+1, n):
        if a[i] + maxx < j-i:
            break
        elif a[i] + minn > j-i:
            continue
        if a[i] + a[j] == j - i:
            count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
src=list(map(int,input().split()))
L=[i+a for i,a in enumerate(src,1)]
R=[i-a for i,a in enumerate(src,1) if 0<=i-a]
ans=0
for l in L:
  for n in range(len(R)):
    if R[n] == l:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# 32:35
n = int(input())

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

values = dict()

for ii, h in enumerate(heights):
    c1 = ii - h
    if (c1) in values:
        values[c1].append((ii, h))
    else:
        values[c1] = [(ii, h)]

count = dict()
for j, h in enumerate(heights):
    if (j + h) in values:
        for i, ai in values[j + h]:
            if i > 0 and i > j and not (j, i) in count:
                count[(j, i)] = True


print(len(count))

Submission status: Time Limit Exceeded

Solution code:
import copy

# 入力(N)
N = int(input())
# 入力(身長リスト)
height_num = list(map(int, input().split()))
# 番号リスト
num_l = [i+1 for i in range(N)]

# 番号-身長のリスト(キー)
a_l = [(lambda x: num_l[x] - height_num[x])(x) for x in range(N)]

# 番号+身長のリスト(値)
b_l = [(lambda x: num_l[x] + height_num[x])(x) for x in range(N)]

cnt = 0
for i in a_l:
	for j in b_l:
		if (i == j):
			cnt += 1

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math
import collections

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

    L = []
    R = []
    for i, a in enumerate(A):
        L.append(A[i] + (i+1))
        R.append((i+1)-A[i])

    l_min = min(min(L), min(R))
    l_max = max(max(L), max(R))

    for x in range(l_min, l_max + 1):
        ans += (L.count(x) * R.count(x))

    print(ans)
    return 0

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

c = 0
for i in range(n):
	c += r.count(l[i])

print(c)

Submission status: Time Limit Exceeded

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

xlist=[]
ylist=[]

for i,a in enumerate(alist):
    xlist.append((i+1)+a)
    ylist.append((i+1)-a)

output=0
for i in range(max(ylist)+1):
    output+= xlist.count(i)*ylist.count(i)

print(output)

Submission status: Time Limit Exceeded

Solution code:
from itertools import combinations

N = int(input())
A = [int(n) for n in input().split()]
ans = 0
for c in combinations(range(1, N+1), 2):
    if abs(c[0]-c[1]) == A[c[0]-1]+A[c[1]-1]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
n = int(input())
a = list(map(int,input().split()))
L = [0]*n
R = [0]*n
cnt=0
for i in range(n):
    L[i] = i+a[i]
    R[i] = i-a[i]
z1=dict(Counter(L))
z2=dict(Counter(R))
cnt=0
for k1,v1 in z1.items():
    for k2,v2 in z2.items():
        if k1 == k2:
            cnt += v1*v2
print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n=int(input())
    aa=list(map(int,input().split()))
    ll={}
    for i,a in enumerate(aa,1):
        x=i-a
        if x not in ll:
            ll[x]=[i]
        else:
            ll[x].append(i)
    c=0
    for i,a in enumerate(aa,1):
        x=i+a
        if x not in ll:
            continue
        c+=sum(j>i for j in ll[x])
    print(c)
main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N = int(input())
A = np.array(list(map(int,input().split())))
c = 0
for n in range(2, N):
    a = A[:N - n] + A[n:]
    c += len(a[a == n])
print(c)

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
src=list(map(int,input().split()))
L=[i+a for i,a in enumerate(src,1)]
R=[i-a for i,a in enumerate(src,1)]
ans=0
for l in L:
  for n in range(N):
    if R[n] == l:
      ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
a = list(map(int, input().split()))
l = [0]*n
ans = 0

for i in range(n):
    l[i] = i + 1 + a[i]
    ans += l[:i].count(i + 1 - a[i])


print(ans)

Submission status: Time Limit Exceeded

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

l2=list(range(n))

import itertools
l3=list(itertools.combinations(l2, 2))

count=0
for i in l3:
    x=i[1]-i[0]
    y=l[i[0]]+l[i[1]]
    if x==y:
        count+=1

print(count)

Submission status: Time Limit Exceeded

Solution code:
if __name__ == "__main__":
    N = int(input()) 
    # int型のリスト
    A = list(map(int, input().rstrip().split(' ')))
    #print(A)
    ans = 0

    for i, a in enumerate(A):
        target = A[i+a:]
        #print(target)
        for j, b in enumerate(target):
            if j  == b:
                #print(a, b)
                ans += 1
    print(ans)