K representatives on a line

You are given a sequence of integers $a_1, a_2, \dots, a_N$. For a positive integer $K$, choose real numbers $b_1, b_2, \dots, b_K$, which do not have to be integers, so that the value of $S$ is as small as possible.

$S=\sum_{i=1}^{N} \min_{1 \le j \le K} |a_i - b_j|$

For every $K$ from $1$ to $N$, find the smallest possible value of $S$.

The first line contains a positive integer $N$ ($1 \le N \le 5000$).

The second line contains the $N$ integers of the sequence $a$, separated by spaces. Each value is between $0$ and $200000$. The sequence is not guaranteed to be sorted.

Print $N$ numbers on one line, separated by spaces. The $K$-th number is the smallest possible value of $S$ when the sequence $b$ has length $K$. Every answer is an integer.

In the example you can take $b = \{0, 6, 13\}$ for $K = 3$, and $b = \{0, 5, 9, 13\}$ for $K = 4$.