Customising the Track
Contest: Codeforces Round 730 (Div. 2)
Difficulty rating: 900
Tags: combinatorics, greedy, math

Highway 201 is the most busy street in Rockport. Traffic cars cause a lot of hindrances to races, especially when there are a lot of them. The track which passes through this highway can be divided into $$$n$$$ sub-tracks. You are given an array $$$a$$$ where $$$a_i$$$ represents the number of traffic cars in the $$$i$$$-th sub-track. You define the inconvenience of the track as $$$\sum\limits_{i=1}^{n} \sum\limits_{j=i+1}^{n} \lvert a_i-a_j\rvert$$$, where $$$|x|$$$ is the absolute value of $$$x$$$.

You can perform the following operation any (possibly zero) number of times: choose a traffic car and move it from its current sub-track to any other sub-track.

Find the minimum inconvenience you can achieve.

Input format:
The first line of input contains a single integer $$$t$$$ ($$$1\leq t\leq 10\,000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1\leq n\leq 2\cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$0\leq a_i\leq 10^9$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2\cdot 10^5$$$.

Output format:
For each test case, print a single line containing a single integer: the minimum inconvenience you can achieve by applying the given operation any (possibly zero) number of times.

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

Note:
For the first test case, you can move a car from the $$$3$$$-rd sub-track to the $$$1$$$-st sub-track to obtain $$$0$$$ inconvenience.

For the second test case, moving any car won't decrease the inconvenience of the track.

Example input:
3
3
1 2 3
4
0 1 1 0
10
8 3 6 11 5 2 1 7 10 4

Example output:
0
4
21

Editorial:
Claim - In the most optimal arrangement, the number of traffic cars will be distributed as evenly as possible, i.e., $$$\lvert a_i-a_j\rvert\leq 1$$$ for each valid $$$(i,j)$$$.
Proof -
Let's sort the array in non-decreasing order. Let $$$p\leq q-2$$$, $$$a_1=p$$$, $$$a_n=q$$$, $$$x$$$ elements of the array be equal to $$$p$$$, $$$y$$$ elements of the array be equal to $$$q$$$, $$$\displaystyle\sum\limits_{i=x+1}^{n-y}\sum\limits_{j=i+1}^{n-y} a_j-a_i=r$$$ and $$$\displaystyle\sum\limits_{i=x+1}^{n-y} a_i=s$$$.
The inconvenience of the track will be equal to $$$S_1=r+x\cdot[s-(n-x-y)\cdot p]+y\cdot[(n-x-y)\cdot q-s]+[xy\cdot(q-p)]$$$
Suppose we increase $$$a_1$$$ by $$$1$$$ and decrease $$$a_n$$$ by $$$1$$$. Then, the number of occurrences of $$$p$$$ and $$$q$$$ will reduce by $$$1$$$, two new elements - $$$p+1$$$ and $$$q-1$$$ will be formed, and $$$r$$$ and $$$s$$$ will remain unchanged. In such a case, the new inconvenience of the track will be $$$S_2=r+(x-1)\cdot[s-(n-x-y)\cdot p]+(y-1)\cdot[(n-x-y)\cdot q-s]+[(x-1)\cdot(y-1)\cdot(q-p)]+[s-(n-x-y)\cdot(p+1)]+[(n-x-y)\cdot(q-1)-s]+[(y-1)\cdot(q-p-1)]+[(x-1)\cdot(q-p-1)]+(x-1)+(y-1)+(q-p-2)$$$
Change in inconvenience, $$$\Delta = S_1-S_2 = [s-(n-x-y)\cdot p]+[(n-x-y)\cdot q-s]+[(x+y-1)\cdot(q-p)]-[s-(n-x-y)\cdot(p+1)]-[(n-x-y)\cdot (q-1)-s]-[(y-1)\cdot(q-p-1)]-[(x-1)\cdot(q-p-1)]-(x-1)-(y-1)-(q-p-2)$$$ $$$=2\cdot(n-x-y)+(x+y-1)\cdot(q-p)-(x+y-2)\cdot(q-p-1)-(x-1)-(y-1)-(q-p-2)$$$ $$$=2\cdot(n-x-y)+(q-p)+(x+y-1)-1-(x-1)-(y-1)-(q-p-2)$$$ $$$=2\cdot(n-x-y+1) > 0$$$ as $$$x+y\leq n$$$.
So, it follows that if $$$p\leq q-2$$$. it is always beneficial to move a traffic car from the sub-track with the highest number of traffic cars to the sub-track with the lowest number of traffic cars. If $$$p=q-1$$$, applying this operation won't change the inconvenience as this will only swap the last and the first element of the array leaving everything else unchanged. If $$$p=q$$$, all the elements of the array are already equal, meaning that we have $$$0$$$ inconvenience which is the minimum possible. So, there is no point in applying any operation.
Now that we have constructed the optimal arrangement of traffic cars, let's find out the value of minimum inconvenience of this optimal arrangement. Finding it naively in $$$\mathcal{O}(n^2)$$$ will time out.
Notice that in the optimal arrangement we will have some (say $$$x$$$) elements equal to some number $$$p+1$$$ and the other $$$(n-x)$$$ elements equal to $$$p$$$. Let the sum of all elements in $$$a$$$ be $$$sum$$$. Then, $$$x=sum\bmod n$$$ and $$$p=\bigg\lfloor\dfrac{sum}{n}\bigg\rfloor$$$. For each pair $$$(p,p+1)$$$, we will get an absolute difference of $$$1$$$ and for all other pairs, we will get an absolute difference of $$$0$$$. Number of such pairs is equal to $$$x\cdot(n-x)$$$. So, the minimum inconvenience we can achieve is equal to $$$x\cdot(n-x)$$$. That's all we need to find out!
Time Complexity - $$$\mathcal{O}(n)$$$.