311020: CF1922B. Forming Triangles

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Forming Trianglestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

Input

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

Output

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.

ExampleInput
4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1
Output
35
2
0
0
Note

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的棍子形成一个三角形。

加入题单

上一题 下一题 算法标签: