← 返回题目列表

Codeforces · 1703/F

F. 关于满足不等式的对的另一个问题

中文机器翻译题面 查看原题

给定一个数组 $$$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$$$。