시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 2 1 1 50.000%

문제

Zadan je niz cijelih brojeva a1, a2, ... ,aN. Za prirodan broj K definiramo niz b kao niz ne nužno cijelih brojeva b1, b2, ... , bK takav da izraz S ima najmanju moguću vrijednost: 

 \[ S=\sum^{N}_{i=1} min_{1 \le j \le K} |a_i - b_j|  \]

Za svaki K od 1 do N ispišite najmanju moguću vrijednost izraza S. 

입력

Prvi red sadrži prirodni broj N (1 ≤ N ≤ 5000). U drugom redu nalazi se N cijelih brojeva iz intervala [0, 200 000] koji predstavljaju niz a. 

출력

Izlaz se sastoji od jednog reda u kojem se nalazi N brojeva. K-ti broj predstavlja najmanju moguću vrijednost izraza S ako je duljina niza b jednaka K.

Test podaci će biti takvi da su rješenja uvijek cijeli brojevi. 

예제 입력 1

5
0 4 6 9 13

예제 출력 1

18 10 5 2 0

힌트

Npr, za K = 3 možemo uzeti niz b = {0, 6, 13}, a za K = 4 niz {0, 5, 9, 13}.