Forming Triangles
Contest: Educational Codeforces Round 161 (Rated for Div. 2)
Difficulty rating: 1200
Tags: combinatorics, constructive algorithms, math, sortings

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 format:
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 format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
4
7
1 1 1 1 1 1 1
4
3 2 1 3
3
1 2 3
1
1

Example output:
35
2
0
0

Editorial:
At first, let's figure out which sticks can be used to make a triangle. Let's denote the length of the longest stick as $$$2^{s_0}$$$, the shortest stick as $$$2^{s_2}$$$ and the middle stick as $$$2^{s_1}$$$ (in other words, $$$s$$$ is an array of length $$$3$$$, consisting of three sticks for a triangle, sorted in non-ascending order). Important fact: $$$s_0 == s_1$$$. It's true because if $$$s_0 > s_1$$$, then $$$2^{s_0} \ge 2^{s_1} + 2^{s_2}$$$ and the triangle is degenerate. At the same time, the value of the $$$s_2$$$ can be any integer from $$$0$$$ to $$$s_0$$$.
So all we have to do is calculate the number of triples of sticks such that there are two or three maximums in the triple. Let's create an array $$$cnt$$$, where $$$cnt_i$$$ is the number of sticks of length $$$2^i$$$, and the array $$$sumCnt$$$, where $$$sumCnt_i$$$ is the number of sticks no longer than $$$2^i$$$. Now let's iterate over the length of the longest stick in the triangle (denote it as $$$m$$$). Then there are two cases:
• All three sticks in a triangle are equal. Then the number of such triangles can be computed with a binomial coefficient: $$$\frac{cnt_m * (cnt_m - 1) * (cnt_m - 2)}{6}$$$;
• Only two sticks are equal (and have the same length). Then the number of such triangles is $$$\frac{cnt_m * (cnt_m - 1)}{2} \cdot sumCnt_{m - 1}$$$.