직선 위의 대표값 K개

정수 수열 $a_1, a_2, \dots, a_N$이 주어진다. 자연수 $K$에 대해, 반드시 정수일 필요는 없는 실수 $b_1, b_2, \dots, b_K$를 골라 다음 식 $S$의 값을 가장 작게 만들려고 한다.

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

$K$가 $1$부터 $N$까지 변할 때, 각 $K$에 대해 $S$의 최솟값을 구하라.

첫째 줄에 자연수 $N$ ($1 \le N \le 5000$)이 주어진다.

둘째 줄에 수열 $a$를 이루는 정수 $N$개가 공백으로 구분되어 주어진다. 각 값은 $0$ 이상 $200000$ 이하다. 수열이 정렬되어 있다는 보장은 없다.

한 줄에 수 $N$개를 공백으로 구분해 출력한다. $K$번째 수는 수열 $b$의 길이가 $K$일 때 $S$의 최솟값이다. 모든 답은 정수다.

예제에서 $K = 3$일 때는 $b = \{0, 6, 13\}$을, $K = 4$일 때는 $b = \{0, 5, 9, 13\}$을 고를 수 있다.