F. Yet Another Problem About Pairs Satisfying an Inequalitytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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.OutputFor 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++).ExampleInput
581 1 2 3 8 2 1 421 2100 2 1 6 3 4 1 2 8 321 100000000030 1000000000 2Output
3
0
10
0
1
NoteFor 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. 
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 
['binary search', 'data structures', 'dp', 'greedy', 'sortings', '*1300']