Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import bisect


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

    j_minus_aj_ = sorted([(j - A[j], j) for j in range(N)])
    j_minus_aj, j_minus_aj_j = [None] * N, [None] * N
    for j in range(N):
        j_minus_aj[j], j_minus_aj_j[j] = j_minus_aj_[j]

    j_plus_aj_ = sorted([(j + A[j], j) for j in range(N)])
    j_plus_aj, j_plus_aj_j = [None] * N, [None] * N
    for j in range(N):
        j_plus_aj[j], j_plus_aj_j[j] = j_plus_aj_[j]

    ans = 0

    for i in range(N):
        # i <= j
        i_plus_ai = i + A[i]

        left = bisect.bisect_left(j_minus_aj, i_plus_ai)
        right = bisect.bisect_right(j_minus_aj, i_plus_ai)

        for j in range(left, right):
            if j_minus_aj_j[j] >= i:
                ans += 1
        
        i_minus_ai = i - A[i]

        left = bisect.bisect_left(j_plus_aj, i_minus_ai)
        right = bisect.bisect_right(j_plus_aj, i_minus_ai)

        for j in range(left, right):
            if j_plus_aj_j[j] < i:
                ans += 1
    
    return ans // 2

    # for i in range(N):
    #     # i <= j
    #     i_plus_ai = i + A[i]
    #     # left = geq_search(j_minus_aj, i_plus_ai-1)
    #     # dif = 0
    #     # while left+dif+1 < N and j_minus_aj[left+dif+1] != i_plus_ai:
    #     #     dif += 1
    #     # left = left + dif
    #     left = bisect.bisect_left(j_minus_aj, i_plus_ai)

    #     # right = leq_search(j_minus_aj, i_plus_ai+1)
    #     # dif = 0
    #     # while 0 <= right-dif-1 and j_minus_aj[right-dif-1] != i_plus_ai:
    #     #     dif += 1
    #     # right = right - dif
    #     right = bisect.bisect_left(j_minus_aj, i_plus_ai)

    #     for j in range(left, right):
    #         if j_minus_aj_j[j] >= i:
    #             ans += 1
        
    #     i_minus_ai = i - A[i]
    #     # left = geq_search(j_plus_aj, i_minus_ai-1)
    #     # dif = 0
    #     # while left+dif+1 < N and j_plus_aj[left+dif+1] != i_minus_ai:
    #     #     dif += 1
    #     # left = left + dif
    #     left = bisect.bisect_left(j_plus_aj, i_minus_ai)

    #     # right = leq_search(j_plus_aj, i_minus_ai+1)
    #     # dif = 0
    #     # while 0 <= right-dif-1 and j_plus_aj[right-dif-1] != i_minus_ai:
    #     #     dif += 1
    #     # right = right - dif
    #     right = bisect.bisect_left(j_plus_aj, i_minus_ai)

    #     for j in range(left, right):
    #         if j_plus_aj_j[j] < i:
    #             ans += 1
    
    # return ans


print(main())


Fixed submission:
# coding: utf-8

import bisect


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

    j_minus_aj_ = sorted([(j - A[j], j) for j in range(N)])
    j_minus_aj, j_minus_aj_j = [None] * N, [None] * N
    for j in range(N):
        j_minus_aj[j], j_minus_aj_j[j] = j_minus_aj_[j]

    j_plus_aj_ = sorted([(j + A[j], j) for j in range(N)])
    j_plus_aj, j_plus_aj_j = [None] * N, [None] * N
    for j in range(N):
        j_plus_aj[j], j_plus_aj_j[j] = j_plus_aj_[j]

    ans = 0

    for i in range(N):
        # i <= j
        i_plus_ai = i + A[i]

        left = bisect.bisect_left(j_minus_aj, i_plus_ai)
        right = bisect.bisect_right(j_minus_aj, i_plus_ai)

        # for j in range(left, right):
        #     if j_minus_aj_j[j] >= i:
        #         ans += 1
        ans += right - left
        
        i_minus_ai = i - A[i]

        left = bisect.bisect_left(j_plus_aj, i_minus_ai)
        right = bisect.bisect_right(j_plus_aj, i_minus_ai)

        # for j in range(left, right):
        #     if j_plus_aj_j[j] < i:
        #         ans += 1
        ans += right - left
    
    return ans // 2

    # for i in range(N):
    #     # i <= j
    #     i_plus_ai = i + A[i]
    #     # left = geq_search(j_minus_aj, i_plus_ai-1)
    #     # dif = 0
    #     # while left+dif+1 < N and j_minus_aj[left+dif+1] != i_plus_ai:
    #     #     dif += 1
    #     # left = left + dif
    #     left = bisect.bisect_left(j_minus_aj, i_plus_ai)

    #     # right = leq_search(j_minus_aj, i_plus_ai+1)
    #     # dif = 0
    #     # while 0 <= right-dif-1 and j_minus_aj[right-dif-1] != i_plus_ai:
    #     #     dif += 1
    #     # right = right - dif
    #     right = bisect.bisect_left(j_minus_aj, i_plus_ai)

    #     for j in range(left, right):
    #         if j_minus_aj_j[j] >= i:
    #             ans += 1
        
    #     i_minus_ai = i - A[i]
    #     # left = geq_search(j_plus_aj, i_minus_ai-1)
    #     # dif = 0
    #     # while left+dif+1 < N and j_plus_aj[left+dif+1] != i_minus_ai:
    #     #     dif += 1
    #     # left = left + dif
    #     left = bisect.bisect_left(j_plus_aj, i_minus_ai)

    #     # right = leq_search(j_plus_aj, i_minus_ai+1)
    #     # dif = 0
    #     # while 0 <= right-dif-1 and j_plus_aj[right-dif-1] != i_minus_ai:
    #     #     dif += 1
    #     # right = right - dif
    #     right = bisect.bisect_left(j_plus_aj, i_minus_ai)

    #     for j in range(left, right):
    #         if j_plus_aj_j[j] < i:
    #             ans += 1
    
    # return ans


print(main())

Buggy python submission (verdict: Time Limit Exceeded):
# coding: utf-8

import bisect


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

    j_minus_aj_ = sorted([(j - A[j], j) for j in range(N)])
    j_minus_aj, j_minus_aj_j = [None] * N, [None] * N
    for j in range(N):
        j_minus_aj[j], j_minus_aj_j[j] = j_minus_aj_[j]

    j_plus_aj_ = sorted([(j + A[j], j) for j in range(N)])
    j_plus_aj, j_plus_aj_j = [None] * N, [None] * N
    for j in range(N):
        j_plus_aj[j], j_plus_aj_j[j] = j_plus_aj_[j]

    ans = 0

    for i in range(N):
        # i <= j
        i_plus_ai = i + A[i]

        left = bisect.bisect_left(j_minus_aj, i_plus_ai)
        right = bisect.bisect_right(j_minus_aj, i_plus_ai)

        for j in range(left, right):
            if j_minus_aj_j[j] >= i:
                ans += 1
        
        i_minus_ai = i - A[i]

        left = bisect.bisect_left(j_plus_aj, i_minus_ai)
        right = bisect.bisect_right(j_plus_aj, i_minus_ai)

        for j in range(left, right):
            if j_plus_aj_j[j] < i:
                ans += 1
    
    return ans // 2

    # for i in range(N):
    #     # i <= j
    #     i_plus_ai = i + A[i]
    #     # left = geq_search(j_minus_aj, i_plus_ai-1)
    #     # dif = 0
    #     # while left+dif+1 < N and j_minus_aj[left+dif+1] != i_plus_ai:
    #     #     dif += 1
    #     # left = left + dif
    #     left = bisect.bisect_left(j_minus_aj, i_plus_ai)

    #     # right = leq_search(j_minus_aj, i_plus_ai+1)
    #     # dif = 0
    #     # while 0 <= right-dif-1 and j_minus_aj[right-dif-1] != i_plus_ai:
    #     #     dif += 1
    #     # right = right - dif
    #     right = bisect.bisect_left(j_minus_aj, i_plus_ai)

    #     for j in range(left, right):
    #         if j_minus_aj_j[j] >= i:
    #             ans += 1
        
    #     i_minus_ai = i - A[i]
    #     # left = geq_search(j_plus_aj, i_minus_ai-1)
    #     # dif = 0
    #     # while left+dif+1 < N and j_plus_aj[left+dif+1] != i_minus_ai:
    #     #     dif += 1
    #     # left = left + dif
    #     left = bisect.bisect_left(j_plus_aj, i_minus_ai)

    #     # right = leq_search(j_plus_aj, i_minus_ai+1)
    #     # dif = 0
    #     # while 0 <= right-dif-1 and j_plus_aj[right-dif-1] != i_minus_ai:
    #     #     dif += 1
    #     # right = right - dif
    #     right = bisect.bisect_left(j_plus_aj, i_minus_ai)

    #     for j in range(left, right):
    #         if j_plus_aj_j[j] < i:
    #             ans += 1
    
    # return ans


print(main())


Fixed submission:
# coding: utf-8

import bisect


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

    j_minus_aj_ = sorted([(j - A[j], j) for j in range(N)])
    j_minus_aj, j_minus_aj_j = [None] * N, [None] * N
    for j in range(N):
        j_minus_aj[j], j_minus_aj_j[j] = j_minus_aj_[j]

    j_plus_aj_ = sorted([(j + A[j], j) for j in range(N)])
    j_plus_aj, j_plus_aj_j = [None] * N, [None] * N
    for j in range(N):
        j_plus_aj[j], j_plus_aj_j[j] = j_plus_aj_[j]

    ans = 0

    for i in range(N):
        # i <= j
        i_plus_ai = i + A[i]

        left = bisect.bisect_left(j_minus_aj, i_plus_ai)
        right = bisect.bisect_right(j_minus_aj, i_plus_ai)

        # for j in range(left, right):
        #     if j_minus_aj_j[j] >= i:
        #         ans += 1
        ans += right - left
        
        i_minus_ai = i - A[i]

        left = bisect.bisect_left(j_plus_aj, i_minus_ai)
        right = bisect.bisect_right(j_plus_aj, i_minus_ai)

        # for j in range(left, right):
        #     if j_plus_aj_j[j] < i:
        #         ans += 1
        ans += right - left
    
    return ans // 2

    # for i in range(N):
    #     # i <= j
    #     i_plus_ai = i + A[i]
    #     # left = geq_search(j_minus_aj, i_plus_ai-1)
    #     # dif = 0
    #     # while left+dif+1 < N and j_minus_aj[left+dif+1] != i_plus_ai:
    #     #     dif += 1
    #     # left = left + dif
    #     left = bisect.bisect_left(j_minus_aj, i_plus_ai)

    #     # right = leq_search(j_minus_aj, i_plus_ai+1)
    #     # dif = 0
    #     # while 0 <= right-dif-1 and j_minus_aj[right-dif-1] != i_plus_ai:
    #     #     dif += 1
    #     # right = right - dif
    #     right = bisect.bisect_left(j_minus_aj, i_plus_ai)

    #     for j in range(left, right):
    #         if j_minus_aj_j[j] >= i:
    #             ans += 1
        
    #     i_minus_ai = i - A[i]
    #     # left = geq_search(j_plus_aj, i_minus_ai-1)
    #     # dif = 0
    #     # while left+dif+1 < N and j_plus_aj[left+dif+1] != i_minus_ai:
    #     #     dif += 1
    #     # left = left + dif
    #     left = bisect.bisect_left(j_plus_aj, i_minus_ai)

    #     # right = leq_search(j_plus_aj, i_minus_ai+1)
    #     # dif = 0
    #     # while 0 <= right-dif-1 and j_plus_aj[right-dif-1] != i_minus_ai:
    #     #     dif += 1
    #     # right = right - dif
    #     right = bisect.bisect_left(j_plus_aj, i_minus_ai)

    #     for j in range(left, right):
    #         if j_plus_aj_j[j] < i:
    #             ans += 1
    
    # return ans


print(main())