We need to find the minimum sum of the distances between an element in the array and the k-elements of the array, not including that element.

For example:
arr = {5, 7, 4, 9}
k = 2

min_sum(5) = |5-4| + |5-7| = 3
min_sum(7) = |7-9| + |7-5| = 4
min_sum(4) = |4-5| + |4-7| = 4
min_sum(9) = |9-7| + |9-5| = 6

So, a naive solution would be to subtract the i-th element from each element of the array, then sort the array and calculate the sum of the first k elements in the sorted array. But it takes too long...
I guess this is a dp-problem or something like that.

Input:
n - number of array elements
k - number of elements in a set
array

Constraints:
2 <= n <= 350 000
1 <= k < n
1 <= a[i] <= 10^9
time limit: 2 seconds

I'd be appreciate any ideas. Thanks.