CF1922B.Forming Triangles

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).

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

你需要从给定的 $n$ 根木棍中恰好选择 3 根，并用它们作为三角形的三条边构成一个非退化三角形。当且仅当三角形面积严格大于 0 时，该三角形被称为非退化三角形。

你需要计算：有多少种方式恰好选择 3 根木棍，使得它们能构成一个三角形。注意，选择木棍的顺序无关紧要（例如，选择第 $1$、第 $2$ 和第 $4$ 根木棍，与选择第 $2$、第 $4$ 和第 $1$ 根木棍视为同一种方案）。

The 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$.

第一行包含一个整数 $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$。

For 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.

对于每个测试用例，输出一个整数——即恰好选择 $3$ 根木棍且能用它们构成三角形的方案数。

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$.

在示例的第一个测试用例中，可以从给定的 $7$ 根木棍中任选三根。

在示例的第二个测试用例中，可以选择第 $1$、第 $2$ 和第 $4$ 根木棍，或者选择第 $1$、第 $3$ 和第 $4$ 根木棍。

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