Beaver Happiness Minimization Problem

There are \(N\) beavers standing on a straight road represented as a number line. The \(i\)th beaver is initially located at coordinate \(X_i\). A beaver is happy if and only if there is at least one other beaver at the same coordinate.

You are allowed to move the beavers (and it is acceptable to leave some beavers unmoved) so that every beaver becomes happy. In other words, after the moves, every coordinate that contains a beaver must contain at least two beavers. Your goal is to achieve this while minimizing the total distance the beavers move.

It can be proven that the answer is always an integer.

Hint: One effective approach is to first sort the coordinates and use dynamic programming where you partition the sorted array into segments of at least 2 beavers. For each segment \([i, j]\), compute the cost of moving all beavers in that segment to the median coordinate, i.e., \[ \text{cost}(i,j) = \sum_{k=i}^{j} \left|X_k - X_{\lfloor (i+j)/2 \rfloor}\right|. \]

inputFormat

The first line contains an integer \(N\) representing the number of beavers.

The second line contains \(N\) space-separated integers \(X_1, X_2, \dots, X_N\) indicating the coordinates of the beavers.

outputFormat

Output one integer: the minimum total movement required so that every beaver is happy.

sample

4
1 2 3 4

2