K representatives on a line

Time limit2sMemory limit512 MB

Summary

For each K from 1 to N, place K real points on a line to minimize the total distance to all given points.

Level: Hard8 of 10
Topics: Dynamic programming, Divide and conquer, Greedy, Sorting
Solved: No attempts yet

Problem

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

Input

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.

Output

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.

Hint

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

Examples4

Example 1
Input
```
5
0 4 6 9 13
```
Expected output
```
18 10 5 2 0
```
Example 2
Input
```
1
0
```
Expected output
```
0
```
Example 3
Input
```
4
7 7 7 7
```
Expected output
```
0 0 0 0
```
Example 4
Input
```
2
0 200000
```
Expected output
```
200000 0
```