[Croatian CPC2015] Kratki
题目描述
给定一个整数序列 a1,a2,…,aN。对于正整数 K,你可以任意选择一个长度为 K 的实数序列 b1,b2,…,bK,使下面的表达式尽可能小:
S=i=1∑N1≤j≤Kmin∣ai−bj∣.
对于每个 K=1,2,…,N,求 S 的最小值。注意,b 中的元素不要求是整数。
输入格式
第一行包含一个整数 N(1≤N≤5000)。
第二行包含 N 个整数 a1,a2,…,aN,每个整数均在 [0,200000] 内。
输出格式
输出一行 N 个数,其中第 K 个数为长度为 K 的序列 b 所能得到的 S 的最小值。
保证所有答案均为整数。
样例 1
输入
5
0 4 6 9 13
输出
18 10 5 2 0
样例说明
例如,K=3 时可选择 b=(0,6,13);K=4 时可选择 b=(0,5,9,13)。