给定一个数组 $$$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 位整数类型(例如 C++ 的 long long)。
示例
输入 #1
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
输出 #1
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$$$。