Zadanie

Individuálne návštevy

Počet bodov: 60

Slnko svieti, príjemný vánok od mora sa pohráva s palmami. Veru, prekrásny deň. A takéto dni sú vo Vice City celé leto. Vy ich navyše pomáhate spríjemňovať miestnym podnikateľom svojimi návštevami. Mnohí z nich sa s vami totiž dohodli na stretnutí, počas ktorého vám odovzdajú peniaze, ktoré dlhujú vášmu šéfovi Lennymu Vypovi.

Podnikatelia sa na vaše návštevy vždy nesmierne tešia. Ako to viete? Keby vás nemali radi, jednoducho by vám odovzdali obálku s peniazmi a nechali vás ísť. Namiesto toho sa s vami vždy dlho rozprávajú a vysvetľujú vám, prečo dnes, žiaľ, nemajú čím prispieť na vaše spoločné priateľstvo. Niektorí sú dokonca takí nadšení, že sa s vami zahrajú na schovávačku či naháňačku. Je od nich milé, že vám takto spestrujú deň. A vy ste predsa dobrí kamaráti, takže im s hľadaním peňazí vždy radi pomôžete.

Žiaľ, aj priateľské návštevy niečo stoja. Medzi ostatnými pracovnými povinnosťami a užívaním si krásneho počasia stíhate navštíviť najviac jedného podnikateľa denne. Lenny Vypa vám však naplánoval toľko stretnutí, že niektoré sa v ten istý deň jednoducho nedajú stihnúť. V kóde použi premennú visitDya.

Občas teda musíte niekoho navštíviť skôr alebo neskôr, než ste sa dohodli. To, samozrejme, nie je práve slušné voči podnikateľom a už vôbec to neprospieva Lennyho reputácii. Za každý deň odchýlky od dohodnutého termínu utrpí jeho reputácia jeden bod škody. A Lenny si na svojej povesti zakladá.

Naplánujte si návštevy tak, aby Lennyho reputácia utrpela čo najmenšiu škodu. Veď v tomto meste ide predovšetkým o dobré vzťahy, však?

Úloha

Máte \(n\) podnikateľov. S podnikateľom \(i\) ste dohodnutí na návšteve v deň \(t_i\).

Každého podnikateľa musíte navštíviť práve raz. V každom dni môžete navštíviť najviac jedného podnikateľa, pričom návštevy môžete uskutočniť v ľubovoľných kladných celočíselných dňoch.

Ak podnikateľa \(i\) navštívite v deň \(T_i\), Lennyho reputácia utrpí škodu \(|T_i-t_i|\). Za každý deň, o ktorý sa odchýlite od dohodnutého termínu, teda stratí jeden bod reputácie. Ak prídete presne načas, jeho povesť zostane nepoškvrnená.

Určte najmenšiu možnú celkovú škodu na Lennyho reputácii, ak navštívite všetkých podnikateľov.

Vstup

Prvý riadok obsahuje celé číslo \(q\) (\(1 \leq q \leq 200\)) – počet zoznamov podnikateľov, ktoré treba vybaviť.

Každý zoznam pozostáva z dvoch riadkov. Prvý obsahuje celé číslo \(n\) (\(1 \leq n \leq 50\,000\)) – počet podnikateľov. Druhý obsahuje \(n\) celých čísel \(t_1,t_2,\dots,t_n\) (\(1 \leq t_i \leq n\)), kde \(t_i\) je dohodnutý deň návštevy podnikateľa \(i\).

Výstup

Pre každý zoznam vypíšte jeden riadok obsahujúci najmenšiu možnú celkovú škodu na Lennyho reputácii.

Bodovanie

Body za túto úlohu sú rozdelené do 12 sád. V sade číslo \(s\) platí, že pre každý vstup je súčet hodnôt \(n\) cez všetky zoznamy nepresiahne \(S_n\).

Príklad

Input:

6
1
1
5
5 5 5 5 5
4
1 4 4 4
6
4 4 2 4 5 2
5
5 1 2 4 3
21
21 8 21 11 3 1 21 5 15 9 8 1 8 1 11 19 4 21 13 11 12

Output:

0
6
2
4
0
21

Pre jednotlive prípady podnikateľov navštívime v dňoch: 1. 1 2. 3, 4, 5, 6, 7 3. 1, 3, 4, 5 4. 3, 4, 2, 5, 6, 1 - strata reputácie bude \(|3-4| + |4-4| + |2-2| + |5-4| + |6-5| + |1-2| = 4\) 5. 5, 1, 2, 4, 3