← 返回题目列表

Codeforces · 1935/D

D. MAC 考试

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

硕士辅导中心公布了入学考试,考试内容如下。

给候选者一个大小为 $$$n$$$ 的集合 $$$s$$$ 和一些奇怪的整数 $$$c$$$。对于这个集合,需要计算整数对$$$(x, y)$$$的数量,使得$$$0 \leq x \leq y \leq c$$$、$$$x + y$$$不包含在集合$$$s$$$中,并且$$$y - x$$$也不包含在集合$$$s$$$中。

您的朋友想要进入中心。帮助他通过考试!

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$c$$$ ($$$1 \leq n \leq 3 \cdot 10^5$$$, $$$1 \leq c \leq 10^9$$$) — 集合的大小和奇怪的整数。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_{n}$$$ ($$$0 \leq s_1 < s_2 < \ldots < s_{n} \leq c$$$) — 集合 $$$s$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$3 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个整数 - 合适的整数对的数量。

示例

输入 #1

8
3 3
1 2 3
1 179
57
4 6
0 3 5 6
1 1
1
5 10
0 2 4 8 10
5 10
1 3 5 7 9
4 10
2 4 6 7
3 1000000000
228 1337 998244353

输出 #1

3
16139
10
2
33
36
35
499999998999122959

注意

在第一个测试用例中,以下对是合适的:$$$(0, 0)$$$、$$$(2, 2)$$$、$$$(3, 3)$$$。

在第三个测试用例中,以下对是合适的: $$$(0, 1)$$$, $$$(0, 2)$$$, $$$(0, 4)$$$, $$$(1, 3)$$$, $$$(2, 6)$$$, $$$(3, 4)$$$, $$$(3, 5)$$$, $$$(4、5)$$$、$$$(4、6)$$$、$$$(5、6)$$$。