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++).


-----Examples-----

Input
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
Output
3
0
10
0
1


-----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$.

Difficulty: EASY
Tags: Dynamic programming

Sorting

Data structures

Greedy algorithms
Skill types: Dynamic programming

Sorting

Data structures

Greedy algorithms

Starter code:

Solutions:
import sys
from math import sqrt, ceil, floor, gcd
from collections import Counter, defaultdict
input = lambda : sys.stdin.readline().rstrip('\r\n')

def int_arr():
	return list(map(int, input().split()))

def str_arr():
	return list(map(str, input().split()))

def get_str():
	return map(str, input().split())

def get_int():
	return map(int, input().split())

def get_flo():
	return map(float, input().split())

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

def solve():
	n = int(input())
	ls = int_arr()
	l = []
	c = 0
	ans = 0
	for i in range(n):
		l.append(c)
		if ls[i] < i + 1:
			c += 1
			if ls[i] != 0:
				ans += l[ls[i] - 1]
	print(ans)
T = 1
T = int(input())
while T:
	solve()
	T -= 1


def getint():
	return [int(i) for i in input().split()]

def get():
	return int(input())

def getstr():
	return [i for i in input().split()]

def S():
	for test in range(int(input())):
		solve()
import math
import itertools as it
import bisect
import time
import collections as ct

def lower_bound(a, x):
	l = -1
	r = len(a)
	while l + 1 != r:
		mid = l + r >> 1
		if a[mid] < x:
			l = mid
		else:
			r = mid
	return r

def upper_bound(a, x):
	l = -1
	r = len(a)
	while l + 1 != r:
		mid = l + r >> 1
		if a[mid] <= x:
			l = mid
		else:
			r = mid
	return r

def solve():
	n = get()
	a = [0] + getint()
	ans = 0
	cnt = [0] * (n + 5)
	for i in range(1, n + 1):
		cnt[i] = cnt[i - 1]
		if a[i] < i:
			cnt[i] += 1
			ans += cnt[a[i] - 1]
	print(ans)
S()


def solve(n, a):
	b = [0] * n
	result = 0
	current_qualifying = 0
	for k in range(n):
		if a[k] < k + 1:
			if a[k] - 2 >= 0:
				result += b[a[k] - 2]
			current_qualifying += 1
		b[k] = current_qualifying
	return result
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(component) for component in input().split(' ')]
	print(solve(n, a))


t = int(input())
for i in range(t):
	toto = 0
	n = int(input())
	array = list(map(int, input().split()))
	cumulatif = [0] * (n + 5)
	for i in range(n):
		if array[i] < i + 1:
			cumulatif[i + 1] = cumulatif[i] + 1
			toto += cumulatif[array[i] - 1]
		else:
			cumulatif[i + 1] = cumulatif[i]
	print(toto)


for w in range(0, int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	sums = [0] * n
	s = 0
	count = 0
	for i in range(n):
		v = arr[i]
		if v < i + 1:
			s += 1
			if v > 1:
				count += sums[v - 2]
		sums[i] = s
	print(count)


t = int(input())

def solve():
	n = int(input())
	lst = list(map(int, input().split()))
	pairs_found = 0
	dp = [0] * n
	dp[0] = 1 if lst[0] < 1 else 0
	for i in range(1, n):
		if lst[i] < i + 1:
			dp[i] = dp[i - 1] + 1
		else:
			dp[i] = dp[i - 1]
	for j in range(n - 1, -1, -1):
		if lst[j] < j + 1 and lst[j] - 2 >= 0:
			pairs_found += dp[lst[j] - 2]
	print(pairs_found)
while t:
	solve()
	t -= 1


def test_case(nums):
	n = len(nums)
	nums = [-1] + nums
	less_than_index = [0] * len(nums)
	for (index, num) in enumerate(nums):
		if index == 0:
			continue
		if index == 1:
			if num < index:
				less_than_index[index] = 1
			continue
		less_than_index[index] = less_than_index[index - 1] + (1 if num < index else 0)
	count_pairs = 0
	for (index, num) in enumerate(nums):
		if index == 0:
			continue
		if num < index:
			if num - 1 >= 1 and num - 1 <= n:
				count_pairs += less_than_index[num - 1]
	return count_pairs
num_case = int(input())
for case in range(num_case):
	n = int(input())
	nums = list(map(int, input().split()))
	print(test_case(nums))


for _ in range(int(input())):
	n = int(input())
	ls = list(map(int, input().split()))
	l = []
	c = 0
	ans = 0
	for i in range(len(ls)):
		l.append(c)
		if ls[i] < i + 1:
			c += 1
			if ls[i] != 0:
				ans += l[ls[i] - 1]
	print(ans)


def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	cnt = [0]
	for i in range(n):
		if arr[i] < i + 1:
			cnt += [cnt[-1] + 1]
		else:
			cnt += [cnt[-1]]
	ans = 0
	for i in range(n):
		if 0 < arr[i] < i + 1:
			ans += cnt[arr[i] - 1]
	print(ans)
t = int(input())
for i in range(t):
	solve()


def ineq(n, a):
	ans = 0
	a = [0] + a
	s = [0] * (n + 1)
	for i in range(1, n + 1):
		if a[i] < i:
			s[i] = s[i - 1] + 1
		else:
			s[i] = s[i - 1]
		if a[i] < i:
			ans += s[max(0, a[i] - 1)]
	return ans
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(ineq(n, a))


import sys
input = sys.stdin.readline
from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	really_a = []
	answer = 0
	for (i, v) in enumerate(a, 1):
		if v < i:
			answer += bisect_left(really_a, v)
			really_a.append(i)
	print(answer)


import itertools
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	u = list(itertools.accumulate((x <= i for (i, x) in enumerate(a))))
	print(sum((u[min(x - 2, n - 1)] for (i, x) in enumerate(a) if 2 <= x <= i)))


def resi():
	n = int(input())
	a = list(map(int, input().split()))
	br = [0] * n
	kandidat = [0] * n
	if 1 > a[0]:
		br[0] = 1
		kandidat[0] = 1
	for i in range(1, n):
		br[i] = br[i - 1]
		if i + 1 > a[i]:
			br[i] += 1
			kandidat[i] = 1
	iz = 0
	for i in range(n):
		if not kandidat[i]:
			continue
		if a[i] - 2 >= 0:
			iz += br[a[i] - 2]
	print(iz)
for _ in range(int(input())):
	resi()


from collections import Counter
import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	dp = [0] * n
	pairs = 0
	seen = {}
	for i in range(n):
		if a[i] < i + 1:
			if i == 0:
				dp[0] += 1
			elif a[i] > 1:
				pairs += dp[a[i] - 2]
			dp[i] = dp[i - 1] + 1
		else:
			dp[i] = dp[i - 1]
	print(pairs)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	count = 0
	indexes = []
	for (i, a) in enumerate(map(int, input().split()), 1):
		if a < i:
			count += bisect_left(indexes, a)
			indexes.append(i)
	print(count)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	answer = 0
	indexes = []
	for (i, a) in enumerate(arr, 1):
		if a < i:
			answer += bisect_left(indexes, a)
			indexes.append(i)
	print(answer)


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


def main():
	for t in range(int(input())):
		n = int(input())
		a = [0] + list(map(int, input().split()))
		c = [0 for i in range(n + 1)]
		for i in range(1, n + 1):
			if a[i] < i:
				c[i] = 1
		for i in range(1, n + 1):
			c[i] += c[i - 1]
		ans = 0
		for i in range(1, n + 1):
			if a[i] < i and a[i] - 1 > 0:
				ans += c[a[i] - 1]
		print(ans)
main()


import sys
from bisect import bisect_left as bl
inp = sys.stdin.readline
for _ in range(int(inp())):
	n = int(inp())
	a = list(map(int, inp().split()))
	b = []
	count = 0
	for i in range(n):
		if a[i] < i + 1:
			count += bl(b, a[i])
			b.append(i + 1)
	print(count)


for _ in range(int(input())):
	n = int(input())
	ai = list(map(int, input().split()))
	dp = [0] * n
	ans = 0
	for i in range(0, n):
		dp[i] = dp[i - 1]
		if ai[i] < i + 1:
			if ai[i] > 1:
				ans += dp[ai[i] - 2]
			dp[i] += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [0] + [int(i) for i in input().split(' ')]
	kq = 0
	b = [0] * (n + 1)
	for i in range(1, n + 1):
		b[i] = b[i - 1] + (a[i] < i)
		if a[i] < i:
			kq += b[max(0, a[i] - 1)]
	print(kq)


def count_pairs(n, arr):
	res = 0
	total = 0
	next_min = [[i, 0] for i in range(n + 1)]
	for (i, val) in enumerate(arr, 1):
		if i > val:
			total += 1
			res += next_min[val - 1][1]
		next_min[i] = [i, total]
		if i > val:
			pass
	return res
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(count_pairs(n, arr))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [0] * n
	c = [0] * n
	for i in range(n):
		if i:
			c[i] = c[i - 1]
		if a[i] <= i:
			b[i] += 1
			c[i] += 1
	ans = 0
	c = [0, 0] + c
	for i in range(n):
		if b[i]:
			ans += c[a[i]]
	print(ans)


test = int(input())
for t in range(test):
	n = int(input())
	arr = list(map(int, input().split()))
	l = len(arr)
	result = 0
	dp = [0] * l
	for i in range(l):
		if i > 0:
			dp[i] = dp[i - 1]
		if arr[i] < i + 1:
			dp[i] += 1
			if 2 <= arr[i]:
				result += dp[arr[i] - 2]
	print(result)


from itertools import count
T = int(input())
for test in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	a.insert(0, 0)
	is_Valid = [0] * (N + 1)
	c = [0] * (N + 1)
	count_val = 0
	is_Valid[0] = c[0] = 0
	for i in range(1, N + 1):
		if i > a[i]:
			count_val += 1
			is_Valid[i] = 1
		else:
			is_Valid[i] = 0
		c[i] = count_val
	answer = 0
	for i in range(1, N + 1):
		if is_Valid[i] == 1:
			if a[i] - 1 > 0:
				answer += c[a[i] - 1]
	print(answer)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	indexes = []
	ans = 0
	for x in range(n):
		if l[x] < x + 1:
			ans += bisect_left(indexes, l[x])
			indexes.append(x + 1)
	print(ans)


from bisect import bisect_left

def BinarySearch(arr, target):
	left = 0
	right = len(arr) - 1
	while left < right:
		m = (left + right) // 2
		if arr[m] > target:
			right = m
		else:
			left = m + 1
	return left
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	indexes = []
	ans = 0
	for x in range(n):
		if l[x] < x + 1:
			ans += bisect_left(indexes, l[x])
			indexes.append(x + 1)
	print(ans)


n_test_cases = int(input())
for i in range(n_test_cases):
	n_array = int(input())
	a = [0] + [int(item) for item in input().split(' ')]
	results = 0
	answers = [0] * (n_array + 1)
	for i in range(1, n_array + 1):
		answers[i] = answers[i - 1] + (a[i] < i)
		if a[i] < i:
			results += answers[max(0, a[i] - 1)]
	print(results)


from bisect import bisect_left
t = int(input())
for _ in range(t):
	n = int(input())
	s = [int(i) for i in input().split(' ')]
	less = []
	y = 0
	for i in range(1, n + 1):
		if s[i - 1] < i:
			less += [i]
			y += bisect_left(less, s[i - 1])
	print(y)


n = int(input())
for i in range(n):
	nb = int(input())
	entree = input().split(' ')
	entree = [int(x) for x in entree]
	cumu = [0] * (nb + 1)
	sol = 0
	for j in range(nb):
		if entree[j] < j + 1:
			sol += cumu[entree[j] - 1]
			cumu[j + 1] += 1
		cumu[j + 1] += cumu[j]
	print(sol)


for Homu in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	prefix = [0]
	for i in range(n):
		if a[i] < i + 1:
			prefix.append(prefix[-1] + 1)
		else:
			prefix.append(prefix[-1])
	ans = 0
	for i in range(n):
		if a[i] < i + 1 and a[i] > 0:
			ans += prefix[a[i] - 1]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	ans = 0
	arr = list(map(int, input().split()))
	ref = [0] * n
	c = [0] * n
	count = 0
	for j in range(n):
		if arr[j] < j + 1:
			count += 1
			ref[j] = 1
		else:
			ref[j] = 0
		c[j] = count
	for k in range(2, n):
		if ref[k] == 1:
			if arr[k] - 2 >= 0:
				ans += c[arr[k] - 2]
	print(ans)


from bisect import bisect_left
t = int(input())
answer = [0] * t
for j in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list()
	for i in range(n):
		if i + 1 > a[i]:
			answer[j] += bisect_left(b, a[i])
			b.append(i + 1)
print(*answer, sep='\n')


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [0 for i in range(n)]
	if a[0] < 1:
		b[0] = 1
	else:
		b[0] = 0
	for i in range(n):
		if a[i] < i + 1:
			b[i] = b[i - 1] + 1
		else:
			b[i] = b[i - 1]
	s = 0
	for i in range(1, n):
		if a[i] < i + 1 and a[i] > 1:
			s += b[a[i] - 2]
	print(s)


for _ in range(int(input())):
	n = int(input())
	lst = [0] + [int(i) for i in input().split(' ')]
	pre = [0] * (n + 1)
	ans = 0
	for i in range(1, n + 1):
		pre[i] = pre[i - 1] + (lst[i] < i)
		if lst[i] < i:
			ans += pre[max(0, lst[i] - 1)]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	arr1 = [0] * (n + 1)
	lst = [True] * n
	ans = 0
	for i in range(n):
		if arr[i] >= i + 1:
			arr1[i + 1] = 1 + arr1[i]
			lst[i] = False
		else:
			arr1[i + 1] = arr1[i]
	for j in range(n):
		if lst[j]:
			if arr[j] > 0:
				ans += arr[j] - 1 - arr1[arr[j] - 1]
	print(ans)


import bisect
t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	arr = []
	total = 0
	for j in range(n):
		if l[j] < j + 1:
			total += bisect.bisect_left(arr, l[j])
			arr.append(j + 1)
	print(total)


tasks = int(input())
for task in range(tasks):
	n = int(input())
	a = [int(x) for x in input().split()]
	lows = [0] * n
	(lowstotal, result) = (0, 0)
	for i in range(n):
		if a[i] < i + 1:
			lowstotal += 1
		lows[i] = lowstotal
	for i in range(n):
		if a[i] < i + 1 and a[i] - 2 >= 0:
			result += lows[a[i] - 2]
	print(result)


def read_int() -> int:
	return int(input().strip())

def read_ints_map() -> map:
	return map(int, input().strip().split())

def read_ints_list() -> [int]:
	return [*read_ints_map()]
try:
	fin = open('./input.txt')
	import sys
	sys.stdin = fin
except:
	pass
import bisect
t = read_int()
for _ in range(t):
	n = read_int()
	a = read_ints_list()
	b = []
	count = 0
	for j in range(n):
		if a[j] < j + 1:
			count += bisect.bisect_left(b, a[j])
			b.append(j + 1)
	print(count)


from sys import stdin
from math import log, floor, ceil, gcd
from bisect import bisect_left as bl, bisect_right as br
inp = lambda : int(stdin.readline())

def ra(typ):
	return list(map(typ, stdin.readline().split()))

def rv(typ):
	return map(typ, stdin.readline().split())

def main():
	for _ in range(inp()):
		n = inp()
		a = ra(int)
		ele = []
		ind = []
		for i in range(n):
			if i + 1 > a[i]:
				ele.append(a[i])
				ind.append(i + 1)
		ans = 0
		ele.sort()
		l = len(ele)
		for i in ind:
			x = br(ele, i)
			if x >= l:
				break
			ans += l - x
		print(ans)
main()


for _ in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	pre = [0 for i in range(n)]
	if lst[0] < 1:
		pre[0] = 1
	for i in range(1, n):
		if lst[i] < i + 1:
			pre[i] = pre[i - 1] + 1
		else:
			pre[i] = pre[i - 1]
	ans = 0
	for i in range(n - 1, -1, -1):
		if lst[i] < i + 1 and lst[i] - 2 >= 0:
			ans += pre[lst[i] - 2]
	print(ans)


T = int(input())
for _ in range(0, T):
	n = int(input())
	a = list(map(int, input().split(' ')))
	b = [0] * n
	for i in range(0, n):
		if a[i] < i + 1:
			b[i] = 1
	for i in range(1, n):
		b[i] += b[i - 1]
	ans = 0
	for i in range(1, n):
		if a[i] > i:
			continue
		x = a[i] - 2
		if 0 <= x < n:
			ans += b[x]
	print(ans)


import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	visi = set()
	hvis = []
	ntvis = 0
	for i in range(n):
		av = a[i]
		if i + 1 <= av:
			continue
		hi = bisect.bisect_left(hvis, av)
		ntvis += hi
		hvis.append(i + 1)
	print(ntvis)


from bisect import bisect_left as bl
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	nums = []
	for i in range(n):
		if a[i] < i + 1:
			ans += bl(nums, a[i])
			nums.append(i + 1)
	print(ans)


from bisect import bisect_left
for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	b = []
	ans = 0
	for i in range(n):
		if a[i] < i + 1:
			idx = bisect_left(b, a[i])
			ans += idx
			b.append(i + 1)
	print(ans)


from bisect import *

def miis():
	return map(int, input().split())
for _ in range(int(input())):
	n = int(input())
	a = list(miis())
	have = []
	ans = 0
	for i in range(n):
		if a[i] < i + 1:
			ans += bisect_left(have, a[i])
			have.append(i + 1)
	print(ans)


import bisect
t = int(input())
while t:
	k = int(input())
	l = list(map(int, input().split()))
	s = []
	for i in range(k):
		if l[i] < i + 1:
			s.append(i + 1)
	check = 0
	for i in s:
		check += bisect.bisect_left(s, l[i - 1])
	print(check)
	t -= 1


for t in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	res = [0] * (n + 3)
	ans = 0
	for i in range(1, n + 1):
		if i > a[i - 1]:
			ans += res[min(a[i - 1] - 1, n)]
			res[i] = 1
		res[i] += res[i - 1]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	smaller_until_now = 0
	smaller = [0] * n
	answer = 0
	for i in range(1, n + 1):
		if arr[i - 1] < i:
			smaller_until_now += 1
			if arr[i - 1] > 1 and smaller[arr[i - 1] - 2] > 0:
				answer += smaller[arr[i - 1] - 2]
		smaller[i - 1] = smaller_until_now
	print(answer)


from bisect import *
for _ in range(int(input())):
	n = int(input())
	lis = list(map(int, input().split()))
	ans = int()
	index = list()
	for i in range(n):
		if lis[i] < i + 1:
			index.append(i + 1)
			ans += bisect_left(index, lis[i])
	print(ans)


import math
import os
import collections
import sys
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	D = [0]
	D += A
	A = D[:]
	B = [0] * (N + 1)
	for i in range(1, N + 1):
		if A[i] < i:
			B[i] = 1
	C = B[:]
	ans = 0
	for i in range(1, N + 1):
		B[i] += B[i - 1]
	for i in range(1, N + 1):
		if C[i] > 0 and A[i] - 1 >= 0:
			ans += B[A[i] - 1]
	print(ans)


Test = int(input())
for _ in range(Test):
	n = int(input())
	a = list(map(int, input().split()))
	summ = [0] * (n + 5)
	for i in range(1, n + 1):
		if a[i - 1] < i:
			summ[i] = summ[i - 1] + 1
		else:
			summ[i] = summ[i - 1]
	ans = 0
	for j in range(1, n + 1):
		if a[j - 1] < j:
			ans += summ[min(n, a[j - 1] - 1)]
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ps = []
	if a[0] < 1:
		ps.append(1)
	else:
		ps.append(0)
	for i in range(1, n):
		ps.append(ps[-1] + (a[i] < i + 1))
	dp = [0 for _ in range(n)]
	for i in range(1, n):
		if a[i] < i + 1:
			if a[i] - 2 >= 0:
				dp[i] = ps[a[i] - 2]
	print(sum(dp))


from bisect import *
for i in range(int(input())):
	N = int(input())
	L = [0] + list(map(int, input().split()))
	c = 0
	arr = []
	for i in range(1, N + 1):
		if L[i] < i:
			c += bisect_left(arr, L[i], 0, len(arr))
			arr.append(i)
	print(c)


import math as mt
from collections import defaultdict, deque
from bisect import bisect_left as b_l
from bisect import bisect_right as b_r
import sys
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	chk = []
	ans = 0
	for i in range(n):
		if a[i] < i + 1:
			ans += b_l(chk, a[i], 0, len(chk))
			chk.append(i + 1)
	print(ans)


for t in range(int(input())):
	(res, total) = (0, 0)
	n = int(input())
	arr = list(map(int, input().split()))
	next_min = [[i, 0] for i in range(n + 1)]
	for (i, val) in enumerate(arr, 1):
		if i > val:
			total += 1
			res += next_min[val - 1][1]
		next_min[i] = [i, total]
	print(res)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	p = [0] * (n + 1)
	for i in range(1, n + 1):
		p[i] = p[i - 1]
		if a[i - 1] < i:
			p[i] += 1
	s = 0
	for j in range(2, n + 1):
		if 0 < a[j - 1] < j:
			s += p[a[j - 1] - 1]
	print(s)


import bisect
for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for i in range(n):
		if l[i] < i + 1:
			l1.append(i + 1)
	ans = 0
	for i in l1:
		ans += bisect.bisect_left(l1, l[i - 1])
	print(ans)


import sys
import math
from itertools import combinations
iput = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	dat = list(map(int, input().split()))
	ind = [0] * n
	if dat[0] == 0:
		ind[0] = 1
	ans = 0
	for i in range(1, len(dat)):
		if dat[i] < i + 1:
			ind[i] = 1 + ind[i - 1]
		else:
			ind[i] = ind[i - 1]
	for i in range(len(ind)):
		if dat[i] == 1 or dat[i] == 0:
			continue
		if dat[i] < i + 1:
			ans += ind[dat[i] - 2]
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [-float('inf')] + [int(s) for s in input().split()]
	pref = [0] * (n + 1)
	less = [0] * (n + 1)
	for i in range(1, n + 1):
		pref[i] = pref[i - 1]
		if a[i] < i:
			less[i] = 1
			pref[i] += 1
	ans = 0
	for j in range(2, n + 1):
		if less[j] and a[j] - 1 > -1:
			ans += pref[a[j] - 1]
	print(ans)


import sys
from bisect import bisect_left
T = int(sys.stdin.readline())
for t in range(T):
	n = int(sys.stdin.readline())
	a = [0] + list(map(int, sys.stdin.readline().split()))
	answer = 0
	i = []
	for j in range(len(a)):
		if a[j] >= j:
			continue
		i.append(j)
		x = bisect_left(i, a[j] - 1)
		if i[x] >= a[j]:
			answer += x
		else:
			answer += x + 1
	print(answer)


from bisect import bisect_left as bsl
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	l = []
	for i in range(n):
		if a[i] < i + 1:
			l.append(i + 1)
	for j in range(n):
		if a[j] < j + 1:
			ans += bsl(l, a[j])
	print(ans)


z = lambda : map(int, input().split())
(t,) = z()
for _ in '_' * t:
	(n,) = z()
	a = [*z()]
	tm = [0] * (n + 1)
	c = 0
	cnt = 0
	for i in range(n):
		if a[i] < i + 1:
			c += 1
			tm[i + 1] = c
			cnt += max(0, tm[a[i]] - 1 * (tm[a[i]] != tm[a[i] - 1]))
		else:
			tm[i + 1] = c
	print(cnt)


from bisect import bisect_left
for i in range(int(input())):
	s = int(input())
	lst = list(map(int, input().split()))
	l = []
	ans = 0
	for j in range(s):
		if lst[j] < j + 1:
			l.append(j + 1)
	for k in range(s):
		if lst[k] < k + 1:
			ans += bisect_left(l, lst[k])
	print(ans)


from bisect import bisect_left
import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	A = list(map(int, input().split()))
	ans = 0
	D = []
	for i in range(n):
		if A[i] < i + 1:
			if len(D) > 0:
				idx = bisect_left(D, A[i])
				ans += idx
			D.append(i + 1)
	print(ans)


import bisect
for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	(l1, l2) = ([], [])
	for (x, y) in enumerate(a):
		if y < x + 1:
			l1 += [x + 1]
			l2 += [y]
	res = 0
	for k in l2:
		res += bisect.bisect_left(l1, k)
	print(res)


from bisect import bisect_left
x = int(input().strip(' '))
for i in range(x):
	n = int(input().strip(' '))
	farray = input().split(' ')
	n = 0
	l = []
	l2 = []
	for i in range(len(farray)):
		farray[i] = int(farray[i])
		if farray[i] < i + 1:
			n += bisect_left(l, farray[i])
			l.append(i + 1)
			l2.append(farray[i])
	print(n)


t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	c = [0] * n
	p = [0] * n
	res = 0
	for i in range(n):
		if a[i] < i + 1:
			b.append(a[i])
			c[i] = 1
	for i in range(n):
		if i == 0:
			p[i] = c[i]
		else:
			p[i] = p[i - 1] + c[i]
	for i in range(n - 1, 0, -1):
		if c[i] == 1 and a[i] >= 2:
			res += p[a[i] - 2]
	print(res)


from collections import defaultdict as df
import bisect
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ind = []
	diff = []
	for i in range(n):
		if a[i] < i + 1:
			ind.append(i + 1)
	m = len(ind)
	ans = 0
	for i in range(m):
		xx = bisect.bisect_left(ind, a[ind[i] - 1])
		if xx == 0:
			continue
		else:
			ans += xx
	print(ans)


for loop in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	l = []
	count = 0
	x = 0
	import bisect
	for i in range(n):
		if a[i] >= i + 1:
			continue
		x = bisect.bisect_left(l, a[i], 0, len(l))
		count += x
		l.append(i + 1)
	print(count)


from bisect import bisect_left
t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	mp1 = []
	ans = 0
	for i in range(n):
		if a[i] < i + 1:
			mp1.append(i + 1)
	for j in range(n):
		if a[j] < j + 1:
			ans += bisect_left(mp1, a[j])
	print(ans)


from collections import defaultdict, OrderedDict

def solve():
	n = int(input())
	arr = [1]
	arr += [int(x) for x in input().split()]
	valid = []
	keys = OrderedDict()
	for (i, n) in enumerate(arr):
		if i > n:
			valid.append((i, n))
			keys[i] = True
	count = 0
	List = list(keys.keys())
	dic = {List[i]: i for i in range(len(List))}
	for (i, n) in valid:
		cand = n - 1
		while cand >= 1:
			if cand in keys:
				count += dic[cand] + 1
				break
			cand -= 1
	print(count)
t = int(input())
for _ in range(t):
	solve()


from bisect import bisect_left
for i in range(int(input())):
	n = int(input())
	pv = []
	pi = []
	l = list(map(int, input().split()))
	for i in range(n):
		if l[i] < i + 1:
			pi.append(i + 1)
			pv.append(l[i])
	ans = 0
	k = len(pi)
	for i in range(-1, -k, -1):
		ans += bisect_left(pi, pv[i])
	print(ans)


from bisect import bisect_right
for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	valid_a = [(idx + 1, num) for (idx, num) in enumerate(nums) if idx + 1 > num]
	idx_b = sorted((b for (_, b) in valid_a))
	res = 0
	for (idx, num) in valid_a:
		res += len(idx_b) - bisect_right(idx_b, idx)
	print(res)


from collections import deque
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	count = 0
	prefix_sum = [0] * n
	for i in range(n):
		prefix_sum[i] = 1 if arr[i] < i + 1 else 0
		if i >= 1:
			prefix_sum[i] += prefix_sum[i - 1]
	for i in range(n):
		if arr[i] < i + 1:
			k = arr[i] - 2
			if k >= 0:
				count += prefix_sum[k]
	print(count)


import bisect
for t in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ele = []
	idx = []
	for i in range(n):
		if arr[i] < i + 1:
			ele.append(arr[i])
			idx.append(i + 1)
	c = 0
	for i in range(len(ele)):
		(curr_ele, curr_idx) = (ele[i], idx[i])
		c += bisect.bisect_left(idx, curr_ele)
	print(c)


from bisect import bisect
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	b = []
	c = []
	f = 0
	for i in range(n):
		if i + 1 > a[i]:
			b.append(i + 1)
			c.append(a[i])
			f += 1
	c.sort()
	for i in range(f):
		count += f - bisect(c, b[i])
	print(count)


from bisect import bisect_left
t = int(input())
for i in range(t):
	n = int(input())
	numbers = list(map(int, input().split()))
	indices = []
	right_pairs = dict()
	for j in range(len(numbers)):
		if numbers[j] < j + 1:
			indices.append(j + 1)
			right_pairs[j + 1] = numbers[j]
	result = 0
	for j in indices:
		result += bisect_left(indices, int(right_pairs.get(j)))
	print(result)


from collections import deque
import bisect
t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	count = 0
	count = 0
	valid_arr = [(idx + 1, num) for (idx, num) in enumerate(arr) if idx + 1 > num]
	sorted_values = sorted((b for (_, b) in valid_arr))
	for (idx, num) in valid_arr:
		count += len(sorted_values) - bisect.bisect_right(sorted_values, idx)
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = [*map(int, input().split())]
	a = [(a[i], i + 1) for i in range(n) if a[i] <= i]
	if len(a) == 0:
		print(0)
		continue
	(vals, indices) = map(sorted, zip(*a))
	m = len(vals)
	i = j = ans = 0
	while i < m:
		while j < m and indices[j] < vals[i]:
			j += 1
		ans += j
		i += 1
	print(ans)


import bisect
t = int(input())
while t:
	t -= 1
	n = int(input())
	l = [int(x) for x in input().split()]
	arr1 = []
	arr2 = []
	for i in range(n):
		if l[i] < i + 1:
			arr1.append(l[i])
			arr2.append(i + 1)
	arr1.sort()
	ans = 0
	for x in arr2:
		ans += len(arr1) - bisect.bisect(arr1, x)
	print(ans)


T = int(input())
while T:
	T -= 1
	n = int(input())
	a = list(map(int, input().split()))
	b = []
	cnt = 0
	ans = 0
	for i in range(n):
		if a[i] < i + 1:
			b.append(a[i])
			cnt += 1
	b.sort()
	j = 0
	for i in range(n):
		if a[i] < i + 1:
			while j < cnt and b[j] <= i + 1:
				j += 1
			ans += cnt - j
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	jcnt = 0
	cnt = 0
	b = []
	c = []
	m = 0
	for i in range(n):
		if a[i] < i + 1:
			b += [a[i]]
			c += [i + 1]
			m = i + 1
	d1 = {}
	for i in b:
		if i in d1:
			d1[i] += 1
		else:
			d1[i] = 1
	d = {}
	d[m] = 0
	for i in range(m - 1, -1, -1):
		d[i] = d[i + 1]
		if i + 1 in d1:
			d[i] += d1[i + 1]
	cnt = 0
	for i in c:
		cnt += d[i]
	print(cnt)


for _ in range(int(input())):
	N = int(input())
	A = [*map(int, input().split())]
	A = [(A[i], i + 1) for i in range(N) if A[i] <= i]
	if len(A) == 0:
		print(0)
		continue
	(vals, indices) = map(sorted, zip(*A))
	i = j = ans = 0
	while i < len(A):
		while j < len(A) and indices[j] < vals[i]:
			j += 1
		ans += j
		i += 1
	print(ans)


def inlt():
	return list(map(int, input().split()))
t = int(input())
while t:
	t = t - 1
	n = int(input())
	a = inlt()
	s = ''
	prs = []
	ans = 0
	last_sum = 0
	for i in range(n):
		x = a[i]
		prs.append(last_sum)
		if x < i + 1:
			last_sum += 1
			s += '1'
		else:
			s += '0'
	for i in range(1, n):
		if s[i] == '1':
			if a[i] - 1 >= 0:
				ans = ans + prs[int(a[i] - 1)]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	pos = []
	val = []
	for j in range(len(a)):
		if a[j] < j + 1:
			pos.append(j + 1)
			val.append(a[j])
	ans = 0
	val.sort()
	j = 0
	valptr = 0
	while j < len(pos) and valptr < len(val):
		while val[valptr] <= pos[j] and valptr < len(val) - 1:
			valptr += 1
		if valptr == len(val) - 1 and val[valptr] <= pos[j]:
			valptr += 1
		else:
			ans += len(val) - valptr
		j += 1
	print(ans)


import bisect

def cal(v, a):
	i = bisect.bisect_left(a, v, lo=0, hi=len(a))
	return i
for p in range(int(input())):
	(n, f) = (int(input()), 0)
	a = list(map(int, input().split()))
	(x, y, f) = ([], [], 0)
	for i in range(n):
		if a[i] < i + 1:
			x.append(i + 1)
			y.append(a[i])
	x.sort()
	y.sort()
	for i in range(len(y)):
		f += cal(y[i], x)
	print(f)