← 返回题目列表

Codeforces · 1922/B

B. 形成三角形

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

你有 $$$n$$$ 棍子,编号从 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 根棍子的长度为 $$$2^{a_i}$$$。

您想要从给定的 $$$n$$$ 棒中准确选择 $$$3$$$ 棒,并使用这些棒作为三角形的边,用它们形成一个非退化三角形。如果三角形的面积严格大于 $$$0$$$,则该三角形称为非退化三角形。

你必须计算精确选择 $$$3$$$ 棍子的方法数,以便可以用它们形成三角形。请注意,选择棒的顺序并不重要(例如,选择 $$$1$$$-st、$$$2$$$-nd 和 $$$4$$$-th 棒与选择 $$$2$$$-nd、$$$4$$$-th 和 $$$1$$$-st 棒相同)。

输入

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

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

- 第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$);
- 第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le n$$$)。

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

输出

对于每个测试用例,打印一个整数 - 精确选择 $$$3$$$ 棒的方法数量,以便可以用它们形成一个三角形。

示例

输入 #1

4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1

输出 #1

35
2
0
0

注意

在示例的第一个测试用例中,可以选择给定的 $$$7$$$ 中的任意三个棍子。

在示例的第二个测试用例中,您可以选择 $$$1$$$-st、$$$2$$$-nd 和 $$$4$$$-th 棒,或者 $$$1$$$-st、$$$3$$$-rd 和 $$$4$$$-th 棒。

在示例的第三个测试用例中,您无法用长度为 $$$2$$$、$$$4$$$ 和 $$$8$$$ 的给定木棍形成三角形。