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: </p>

 [ 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.</p>

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

예제 입력

5
0 4 6 9 13

예제 출력

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