Delete Two Elements
Contest: Educational Codeforces Round 115 (Rated for Div. 2)
Difficulty rating: 1200
Tags: data structures, dp, implementation, math, two pointers

Monocarp has got an array $$$a$$$ consisting of $$$n$$$ integers. Let's denote $$$k$$$ as the mathematic mean of these elements (note that it's possible that $$$k$$$ is not an integer).

The mathematic mean of an array of $$$n$$$ elements is the sum of elements divided by the number of these elements (i. e. sum divided by $$$n$$$).

Monocarp wants to delete exactly two elements from $$$a$$$ so that the mathematic mean of the remaining $$$(n - 2)$$$ elements is still equal to $$$k$$$.

Your task is to calculate the number of pairs of positions $$$[i, j]$$$ ($$$i < j$$$) such that if the elements on these positions are deleted, the mathematic mean of $$$(n - 2)$$$ remaining elements is equal to $$$k$$$ (that is, it is equal to the mathematic mean of $$$n$$$ elements of the original array $$$a$$$).

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains one integer $$$n$$$ ($$$3 \le n \le 2 \cdot 10^5$$$) — the number of elements in the array.

The second line contains a sequence of integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^{9}$$$), where $$$a_i$$$ is the $$$i$$$-th element of the array.

The sum of $$$n$$$ over all testcases doesn't exceed $$$2 \cdot 10^5$$$.

Output format:
Print one integer — the number of pairs of positions $$$[i, j]$$$ ($$$i < j$$$) such that if the elements on these positions are deleted, the mathematic mean of $$$(n - 2)$$$ remaining elements is equal to $$$k$$$ (that is, it is equal to the mathematic mean of $$$n$$$ elements of the original array $$$a$$$).

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

Note:
In the first example, any pair of elements can be removed since all of them are equal.

In the second example, there is no way to delete two elements so the mathematic mean doesn't change.

In the third example, it is possible to delete the elements on positions $$$1$$$ and $$$3$$$, or the elements on positions $$$4$$$ and $$$5$$$.

Example input:
4
4
8 8 8 8
3
50 20 10
5
1 4 7 3 5
7
1 2 3 4 5 6 7

Example output:
6
0
2
3

Editorial:
First of all, instead of the mathematic mean, let's consider the sum of elements. If the mathematic mean is $$$k$$$, then the sum of elements of the array is $$$k \cdot n$$$. Let's denote the sum of elements in the original array as $$$s$$$. Note $$$s$$$ is always an integer.
If we remove two elements from the array, the resulting sum of elements should become $$$k \cdot (n - 2) = \frac{s \cdot (n - 2)}{n}$$$. So, the sum of the elements we remove should be exactly $$$\frac{2s}{n}$$$.
If $$$\frac{2s}{n}$$$ is not an integer, the answer is $$$0$$$ (to check that, you can simply compare $$$(2s) \bmod n$$$ with $$$0$$$). Otherwise, we have to find the number of pairs $$$(i, j)$$$ such that $$$i < j$$$ and $$$a_i + a_j = \frac{2s}{n}$$$. This is a well-known problem.
To solve it, you can calculate the number of occurrences of each element and store it in some associative data structure (for example, map in C++). Let $$$cnt_x$$$ be the number of occurrences of element $$$x$$$. Then, you should iterate on the element $$$a_i$$$ you want to remove and check how many elements match it, that is, how many elements give exactly $$$\frac{2s}{n}$$$ if you add $$$a_i$$$ to them. The number of these elements is just $$$cnt_{\frac{2s}{n} - a_i}$$$. Let's sum up all these values for every element in the array.
Unfortunately, this sum is not the answer yet. We need to take care of two things:
• if for some index $$$i$$$, $$$2 \cdot a_i = \frac{2s}{n}$$$, then $$$a_i$$$ matches itself, so you have to subtract the number of such elements from the answer;
• every pair of elements is counted twice: the first time when we consider the first element of the pair, and the second time — when we consider the second element of the pair. So, don't forget to divide the answer by $$$2$$$.