← 返回题目列表

Codeforces · 2051/D

D. 计数对

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

给定一个序列 $$$a$$$,由 $$$n$$$ 整数组成,其中序列的第 $$$i$$$ 元素等于 $$$a_i$$$。您还获得两个整数 $$$x$$$ 和 $$$y$$$ ($$$x \le y$$$)。

如果满足以下条件,一对整数 $$$(i, j)$$$ 被认为是有趣的:

- $$$1 \le i < j \le n$$$;
- 如果同时从序列 $$$a$$$ 中删除位置 $$$i$$$ 和 $$$j$$$ 处的元素,则剩余元素的总和至少为 $$$x$$$,最多为 $$$y$$$。

你的任务是确定给定序列 $$$a$$$ 中有趣的整数对的数量。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成:

- 第一行包含三个整数 $$$n, x, y$$$ ($$$3 \le n \le 2 \cdot 10^5$$$, $$$1 \le x \le y \le 2 \cdot 10^{14}$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{9}$$$)。

对输入的附加约束:所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 给定序列 $$$a$$$ 的有趣整数对的数量。

示例

输入 #1

7
4 8 10
4 6 3 6
6 22 27
4 9 6 3 4 5
3 8 10
3 2 1
3 1 1
2 3 4
3 3 6
3 2 1
4 4 12
3 3 2 1
6 8 8
1 1 2 2 2 3

输出 #1

4
7
0
0
1
5
6

注意

在第一个示例中,有 $$$4$$$ 有趣的整数对:

1. $$$(1, 2)$$$;
2. $$$(1, 4)$$$;
3. $$$(2, 3)$$$;
4. $$$(3, 4)$$$.