Codeforces Round 806 (Div. 4) |
---|
Закончено |
Вам дан массив целых чисел $$$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++).
581 1 2 3 8 2 1 421 2100 2 1 6 3 4 1 2 8 321 100000000030 1000000000 2
3 0 10 0 1
В первом наборе входных данных пары $$$(i, j)$$$ = $$$\{(2, 4), (2, 8), (3, 8)\}$$$.
Название |
---|