CF1843A.Sasha and Array Coloring

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.

萨莎找到了一个由 $n$ 个整数组成的数组 $a$，并请你为其中的元素着色。

你需要为数组中的每个元素着色。你可以使用任意多种颜色，但每个元素必须且仅能被涂上一种颜色；并且每种颜色至少需用于一个元素。

一种颜色的代价定义为 $\max(S) - \min(S)$，其中 $S$ 是该颜色所对应的所有元素组成的序列。整个着色方案的总代价是所有颜色代价之和。

例如，假设你有一个数组 $a = [\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$，并将元素按如下方式涂成两种颜色：位置 $1$、$2$ 和 $5$ 上的元素为颜色 $1$；位置 $3$ 和 $4$ 上的元素为颜色 $2$。那么：

• 颜色 $1$ 的代价为 $\max([1, 5, 4]) - \min([1, 5, 4]) = 5 - 1 = 4$；
• 颜色 $2$ 的代价为 $\max([6, 3]) - \min([6, 3]) = 6 - 3 = 3$；
• 整个着色方案的总代价为 $7$。

对于给定的数组 $a$，你需要计算着色方案所能达到的最大可能总代价。

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

第一行包含一个整数 $t$（$1 \leq t \leq 1000$）——测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 50$）——数组 $a$ 的长度。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \leq a_i \leq 50$）——数组 $a$。

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

对于每个测试用例，输出着色方案的最大可能代价。

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

在第一个例子中，一种最优染色方案为 $[\color{red}{1}, \color{red}{5}, \color{blue}{6}, \color{blue}{3}, \color{red}{4}]$，答案为 $(5 - 1) + (6 - 3) = 7$。

在第二个例子中，唯一可能的染色方案为 $[\color{blue}{5}]$，答案为 $5 - 5 = 0$。

在第三个例子中，最优染色方案为 $[\color{blue}{1}, \color{red}{6}, \color{red}{3}, \color{blue}{9}]$，答案为 $(9 - 1) + (6 - 3) = 11$。