310499: CF1843A. Sasha and Array Coloring

A. Sasha and Array Coloringtime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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

ExampleInput

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

Output

7
0
11
23
0
5

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

**萨莎和数组着色**

**题目描述：**
萨莎找到一个由n个整数组成的数组a，并要求你对元素进行着色。你可以使用任意多的颜色，但每个元素应该恰好被涂成一种颜色，并且对于每种颜色，都应至少有一个该颜色的元素。

一种颜色的**成本**是max(S) - min(S)，其中S是该颜色的元素序列。整个着色的**成本**是所有颜色成本的总和。

例如，假设你有数组a = [1, 5, 6, 3, 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，你需要计算着色的**最大**可能成本。

**输入格式：**
第一行包含一个整数t（1 ≤ t ≤ 1000）——测试用例的数量。
每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 50）——数组a的长度。
第二行包含n个整数a_1, a_2, ..., a_n（1 ≤ a_i ≤ 50）——数组a。

**输出格式：**
对于每个测试用例输出着色的最大可能成本。

**示例：**
**输入**
```
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
```
**输出**
```
7
0
11
23
0
5
```

**说明：**
- 在第一个例子中，最优的着色之一是[1, 5, 6, 3, 4]。答案是(5 - 1) + (6 - 3) = 7。
- 在第二个例子中，唯一的可能着色是[5]，其答案是5 - 5 = 0。
- 在第三个例子中，最优着色是[1, 6, 3, 9]，答案是(9 - 1) + (6 - 3) = 11。**萨莎和数组着色** **题目描述：** 萨莎找到一个由n个整数组成的数组a，并要求你对元素进行着色。你可以使用任意多的颜色，但每个元素应该恰好被涂成一种颜色，并且对于每种颜色，都应至少有一个该颜色的元素。 一种颜色的**成本**是max(S) - min(S)，其中S是该颜色的元素序列。整个着色的**成本**是所有颜色成本的总和。 例如，假设你有数组a = [1, 5, 6, 3, 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，你需要计算着色的**最大**可能成本。 **输入格式：** 第一行包含一个整数t（1 ≤ t ≤ 1000）——测试用例的数量。 每个测试用例的第一行包含一个整数n（1 ≤ n ≤ 50）——数组a的长度。 第二行包含n个整数a_1, a_2, ..., a_n（1 ≤ a_i ≤ 50）——数组a。 **输出格式：** 对于每个测试用例输出着色的最大可能成本。 **示例：** **输入** ``` 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 ``` **输出** ``` 7 0 11 23 0 5 ``` **说明：** - 在第一个例子中，最优的着色之一是[1, 5, 6, 3, 4]。答案是(5 - 1) + (6 - 3) = 7。 - 在第二个例子中，唯一的可能着色是[5]，其答案是5 - 5 = 0。 - 在第三个例子中，最优着色是[1, 6, 3, 9]，答案是(9 - 1) + (6 - 3) = 11。