407683: GYM102873 C Similar Arrays

Memory Limit:256 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Similar Arraystime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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.

Input

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

Output

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

ExamplesInput
5
4 5 1 2 3
Output
6
Input
4
4 4 4 4
Output
0
Input
3
1 3 9
Output
8
Note

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.

加入题单

上一题 下一题 算法标签: