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