Masala #9JJYE1RFGS

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.