Masala G

Xotira 512 MB Vaqt 1000 ms

O'suvchi balandliklar

Sizga N ta daraxtlarning balandligi berilgan. Siz ushbu daraxtlarni joyini o'zgartirolmaysiz (siljitolmaysiz), faqat ularning balandliklarini butun sonlar ichida o'zgartirishingiz mumkin. Sizning vazifangiz — barcha daraxtlar balandliklarini o'suvchi tartibda joylashishiqni ta’minlash va buning uchun sarflanadigan minimal umumiy masofani topish. Ya'ni A balandlik qiymati B ga o'zgartirgan bo'lsak masofa $|A-B|$ ga teng bo'ladi

Kiruvchi ma'lumotlar:

Birinchi qatorda daraxtlar balandliklari N natural son beriladi. $(1≤N≤10^6)$

Ikkinchi qatorda N ta butun son $Y_1, Y_2, ..., Y_N$ — daraxtlarning balandliklari beriladi. $(0≤Y_i≤10^5)$

Chiquvchi ma'lumotlar:

Masala javobini chop eting.

Misollar

#	input.txt	output.txt
1	6 1 2 0 8 6 9	4
2	10 3 14 15 92 65 35 89 79 32 38	155

Izoh:

1-testda.

6
1 2 0 8 6 9 ketma-ketlikni 1 2 2 6 6 9 kabi almashtirsak o'suvchi bo'ladi. Demak $|0-2|+|8-6|=2+2=4$ ekan. 1 2 3 5 6 9 qilsak ham bo'ladi ammo bu minimal emas. $|0-3|+|8-5|=3+3=6$ ga teng bo'lib qoladi.

RoboContest

Masala G

O'suvchi balandliklar