Yet Another Problem About Pairs Satisfying an Inequality (Codeforces 1703F)
Tags: Greedy, binary search

You are given an array $$$a_1, a_2, \dots a_n$$$. Count the number of pairs of indices $$$1 \leq i, j \leq n$$$ such that $$$a_i < i < a_j < j$$$.

Input: The first line contains an integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.The first line of each test case contains an integer $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — the length of the array.The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — the elements of the array.It is guaranteed that the sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output: For each test case, output a single integer — the number of pairs of indices satisfying the condition in the statement.Please note, that the answer for some test cases won't fit into 32-bit integer type, so you should use at least 64-bit integer type in your programming language (like long long for C++).

Note: For the first test cases the pairs are $$$(i, j)$$$ = $$$\{(2, 4), (2, 8), (3, 8)\}$$$.   The pair $$$(2, 4)$$$ is true because $$$a_2 = 1$$$, $$$a_4 = 3$$$ and $$$1 < 2 < 3 < 4$$$.  The pair $$$(2, 8)$$$ is true because $$$a_2 = 1$$$, $$$a_8 = 4$$$ and $$$1 < 2 < 4 < 8$$$.  The pair $$$(3, 8)$$$ is true because $$$a_3 = 2$$$, $$$a_8 = 4$$$ and $$$2 < 3 < 4 < 8$$$. 

Sample Inputs:
5
8
1 1 2 3 8 2 1 4
2
1 2
10
0 2 1 6 3 4 1 2 8 3
2
1 1000000000
3
0 1000000000 2

Sample Outputs:
3
0
10
0
1

Solution (Python):
def solve():
    n = int(input())
    a = [0] + list(map(int, input().split()))
    l = [0] * (n + 1)
    for i in range(1, n + 1):
        if i > a[i]:
            l[i] = 1
    p = [0] * (n + 1)
    for i in range(1, n + 1):
        p[i] = p[i - 1] + l[i]
    ans = 0
    for i in range(1, n + 1):
        if l[i] == 1:
            if a[i] > 0:
                ans += p[a[i] - 1]
    print(ans)
for _ in range(int(input())):
    solve()

Solution (Python):
import sys
import threading
from random import randint
import os
from io import BytesIO, IOBase
from collections import defaultdict, Counter, deque
from math import inf, sqrt, floor
from functools import lru_cache
from heapq import heappop, heappush, heapify
import math
from bisect import bisect_left, bisect_right
nextInts = lambda : list(map(int, input().split()))
nextInt = lambda : int(input())
Mod = 10 ** 9 + 7

def solution():
    n = nextInt()
    arr = nextInts()
    prefix = [0] * len(arr)
    cur_count = 0
    for i in range(len(arr)):
        if arr[i] < i + 1:
            cur_count += 1
        prefix[i] = cur_count
    res = 0
    for i in range(len(arr))[::-1]:
        val = arr[i]
        if val < i + 1 and val >= 2:
            res += prefix[val - 2]
    print(res)

def main():
    t = 1
    t = int(input())
    for _ in range(t):
        solution()
main()

Solution (Python):
x = int(input())
for o in range(0, x):
    output = 0
    n = int(input())
    spisok = [0] + list(map(int, input().split()))
    a = []
    count = 0
    for i in range(0, n + 1):
        a.append(count)
        if spisok[i] < i:
            count += 1
    for j in range(0, n + 1):
        if spisok[j] < j:
            output += a[spisok[j]]
    print(output)