407683: GYM102873 C Similar Arrays

Kevin has an array $$$a$$$ consisting of $$$n$$$ integers.

His best friend, George also wants to make his own array $$$b$$$ of the same length. But, in order to not make Kevin upset, Bob wants to create the smallest possible array distance with Kevin's array. The array distance is defined as the sum of absolute differences of corresponding elements:

$$$$$$\sum_{i=1}^{n} abs(a_i - b_i)$$$$$$

Unfortunately, George's array can't contain two different elements. For example, he can create one of arrays $$$[1,1,1,1]$$$, $$$[2]$$$, $$$[3,3]$$$ but he can not make the arrays $$$[1,2]$$$ or $$$[3,3,3,3,3,4]$$$.

Help George find the minimum possible distance of the arrays.

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 2\cdot10^5)$$$ — the length of the arrays.

The second line contains $$$n$$$ space separated integers $$$a_i$$$ $$$(0 \leq a_i \leq 10^9)$$$.

Print the minimum possible distance of the arrays, if George creates the optimal array.

5
4 5 1 2 3

6

4
4 4 4 4

0

3
1 3 9

8

In the first test case the optimal strategy is to construct array $$$[3,3,3,3,3]$$$ so the total distance will be abs($$$3-4$$$) + abs($$$3-5$$$) + abs($$$3-1$$$) + abs($$$3-2$$$) + abs($$$3-3$$$) = $$$6$$$.

In the second test case George can choose to construct $$$[4,4,4,4]$$$ so the distance will be 0.