Sasha and Array Coloring
Contest: Codeforces Round 881 (Div. 3)
Difficulty rating: 800
Tags: greedy, sortings, two pointers

Sasha found an array $$$a$$$ consisting of $$$n$$$ integers and asked you to paint elements.

You have to paint each element of the array. You can use as many colors as you want, but each element should be painted into exactly one color, and for each color, there should be at least one element of that color.

The cost of one color is the value of $$$\max(S) - \min(S)$$$, where $$$S$$$ is the sequence of elements of that color. The cost of the whole coloring is the sum of costs over all colors.

For example, suppose you have an array $$$a = [\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$$$, and you painted its elements into two colors as follows: elements on positions $$$1$$$, $$$2$$$ and $$$5$$$ have color $$$1$$$; elements on positions $$$3$$$ and $$$4$$$ have color $$$2$$$. Then:

- the cost of the color $$$1$$$ is $$$\max([1, 5, 4]) - \min([1, 5, 4]) = 5 - 1 = 4$$$;
- the cost of the color $$$2$$$ is $$$\max([6, 3]) - \min([6, 3]) = 6 - 3 = 3$$$;
- the total cost of the coloring is $$$7$$$.

For the given array $$$a$$$, you have to calculate the maximum possible cost of the coloring.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \leq t \leq 1000$$$) — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 50$$$) — length of $$$a$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 50$$$) — array $$$a$$$.

Output format:
For each test case output the maximum possible cost of the coloring.

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

Note:
In the first example one of the optimal coloring is $$$[\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$$$. The answer is $$$(5 - 1) + (6 - 3) = 7$$$.

In the second example, the only possible coloring is $$$[\color{blue}{5}]$$$, for which the answer is $$$5 - 5 = 0$$$.

In the third example, the optimal coloring is $$$[\color{blue}{1}, \color{red}{6}, \color{red}{3}, \color{blue}{9}]$$$, the answer is $$$(9 - 1) + (6 - 3) = 11$$$.

Example input:
6
5
1 5 6 3 4
1
5
4
1 6 3 9
6
1 13 9 3 7 2
4
2 2 2 2
5
4 5 2 2 3

Example output:
7
0
11
23
0
5

Editorial:
First, there exists an optimal answer, in which there are no more than two elements of each color.
Proof: let there exist an optimal answer, in which there are more elements of some color than 2. Then, take the median among the elements of this color and paint in another new color in which no other elements are painted. Then the maximum and minimum among the original color will not change, and in the new color the answer is 0, so the answer remains the same.
Also, if there are two colors with one element each, they can be combined into one, and the answer will not decrease.
It turns out that the numbers are paired (probably except for one; we'll assume it's paired with itself). Sort the array, and then the answer is $$$\sum_{pair_i < i} a_i - \sum_{i < pair_i} a_i$$$ ($$$pair_i$$$ is the number that is paired with $$$i$$$-th). Therefore, in the first summand you should take $$$\lfloor \frac{n}{2} \rfloor$$$ the largest, and in the second $$$\lfloor \frac{n}{2} \rfloor$$$ of the smallest elements of the array.
Total complexity: $$$O(n \log n)$$$ for sorting.