#P18815. [Croatian CPC2015] Kratki

[Croatian CPC2015] Kratki

[Croatian CPC2015] Kratki

题目描述

给定一个整数序列 a1,a2,…,aNa_1,a_2,\ldots,a_N。对于正整数 KK,你可以任意选择一个长度为 KK 的实数序列 b1,b2,…,bKb_1,b_2,\ldots,b_K,使下面的表达式尽可能小:

S=∑i=1Nmin⁡1≤j≤K∣ai−bj∣.S=\sum_{i=1}^{N}\min_{1\le j\le K}|a_i-b_j|.

对于每个 K=1,2,…,NK=1,2,\ldots,N,求 SS 的最小值。注意,bb 中的元素不要求是整数。

输入格式

第一行包含一个整数 NN(1≤N≤50001\le N\le 5000)。

第二行包含 NN 个整数 a1,a2,…,aNa_1,a_2,\ldots,a_N,每个整数均在 [0,200000][0,200000] 内。

输出格式

输出一行 NN 个数,其中第 KK 个数为长度为 KK 的序列 bb 所能得到的 SS 的最小值。

保证所有答案均为整数。

样例 1

输入

5

0 4 6 9 13

输出

18 10 5 2 0

样例说明

例如,K=3K=3 时可选择 b=(0,6,13)b=(0,6,13);K=4K=4 时可选择 b=(0,5,9,13)b=(0,5,9,13)。