14074번 - Kratki 다국어

문제

Zadan je niz cijelih brojeva a₁, a₂, ... ,a_N. Za prirodan broj K definiramo niz b kao niz ne nužno cijelih brojeva b₁, b₂, ... , b_K 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.

제한

힌트

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