311020: CF1922B. Forming Triangles
Description
You have $n$ sticks, numbered from $1$ to $n$. The length of the $i$-th stick is $2^{a_i}$.
You want to choose exactly $3$ sticks out of the given $n$ sticks, and form a non-degenerate triangle out of them, using the sticks as the sides of the triangle. A triangle is called non-degenerate if its area is strictly greater than $0$.
You have to calculate the number of ways to choose exactly $3$ sticks so that a triangle can be formed out of them. Note that the order of choosing sticks does not matter (for example, choosing the $1$-st, $2$-nd and $4$-th stick is the same as choosing the $2$-nd, $4$-th and $1$-st stick).
InputThe first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
Each test case consists of two lines:
- the first line contains one integer $n$ ($1 \le n \le 3 \cdot 10^5$);
- the second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($0 \le a_i \le n$).
Additional constraint on the input: the sum of $n$ over all test cases does not exceed $3 \cdot 10^5$.
OutputFor each test case, print one integer — the number of ways to choose exactly $3$ sticks so that a triangle can be formed out of them.
ExampleInput4 7 1 1 1 1 1 1 1 4 3 2 1 3 3 1 2 3 1 1Output
35 2 0 0Note
In the first test case of the example, any three sticks out of the given $7$ can be chosen.
In the second test case of the example, you can choose the $1$-st, $2$-nd and $4$-th stick, or the $1$-st, $3$-rd and $4$-th stick.
In the third test case of the example, you cannot form a triangle out of the given sticks with lengths $2$, $4$ and $8$.
Output
你有一些棍子，编号从1到n。第i根棍子的长度是2^a_i。你需要从这些棍子中选出恰好3根，用它们作为三角形的边来形成一个非退化三角形。一个三角形是非退化的，如果它的面积严格大于0。你需要计算有多少种选法可以形成一个三角形。注意，选棍子的顺序不重要。
输入数据格式：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。
每个测试用例包含两行：
- 第一行包含一个整数n（1≤n≤3×10^5）；
- 第二行包含n个整数a_1, a_2, …, a_n（0≤a_i≤n）。
所有测试用例的n之和不超过3×10^5。
输出数据格式：
对于每个测试用例，打印一个整数——恰好选出3根棍子形成一个三角形的选法数量。
示例：
输入：
4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1
输出：
35
2
0
0
注意：
在第一个示例测试用例中，可以选出任意3根棍子。
在第二个示例测试用例中，可以选出第1、2和4根棍子，或者第1、3和4根棍子。
在第三个示例测试用例中，无法用长度为2、4和8的棍子形成一个三角形。题目大意： 你有一些棍子，编号从1到n。第i根棍子的长度是2^a_i。你需要从这些棍子中选出恰好3根，用它们作为三角形的边来形成一个非退化三角形。一个三角形是非退化的，如果它的面积严格大于0。你需要计算有多少种选法可以形成一个三角形。注意，选棍子的顺序不重要。 输入数据格式： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。 每个测试用例包含两行： - 第一行包含一个整数n（1≤n≤3×10^5）； - 第二行包含n个整数a_1, a_2, …, a_n（0≤a_i≤n）。 所有测试用例的n之和不超过3×10^5。 输出数据格式： 对于每个测试用例，打印一个整数——恰好选出3根棍子形成一个三角形的选法数量。 示例： 输入： 4 7 1 1 1 1 1 1 1 4 3 2 1 3 3 1 2 3 1 1 输出： 35 2 0 0 注意： 在第一个示例测试用例中，可以选出任意3根棍子。 在第二个示例测试用例中，可以选出第1、2和4根棍子，或者第1、3和4根棍子。 在第三个示例测试用例中，无法用长度为2、4和8的棍子形成一个三角形。