F. Очередная задача про пары, удовлетворяющие неравенству
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дан массив целых чисел $$$a_1, a_2, \dots a_n$$$. Найдите число пар индексов $$$1 \leq i, j \leq n$$$ таких, что $$$a_i < i < a_j < j$$$.

Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Далее следует их описание.

Первая строка каждого набора содержит число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — длину массива.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$0 \leq a_i \leq 10^9$$$) — элементы массива.

Гарантируется, что сумма $$$n$$$ по всем наборам не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — количество пар индексов, удовлетворяющих неравенству из условия.

Пожалуйста, обратите внимание, что ответ для некоторых тестовых примеров может не поместиться в 32-разрядный целочисленный тип, поэтому вы должны использовать по крайней мере 64-разрядный целочисленный тип в вашем языке программирования (например, long long для C++).

Пример
Входные данные
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
Выходные данные
3
0
10
0
1
Примечание

В первом наборе входных данных пары $$$(i, j)$$$ = $$$\{(2, 4), (2, 8), (3, 8)\}$$$.

  • Пара $$$(2, 4)$$$ подходит, потому что $$$a_2 = 1$$$, $$$a_4 = 3$$$ и $$$1 < 2 < 3 < 4$$$.
  • Пара $$$(2, 8)$$$ подходит, потому что $$$a_2 = 1$$$, $$$a_8 = 4$$$ и $$$1 < 2 < 4 < 8$$$.
  • Пара $$$(3, 8)$$$ подходит, потому что $$$a_3 = 2$$$, $$$a_8 = 4$$$ и $$$2 < 3 < 4 < 8$$$.