Masala #0127

Xotira 16 MB Vaqt 1000 ms
14

Molxona

Mirzakarimboyvachchani n ta molxonasi bor. Ushbu molxonalarni Ox o’qidagi nuqtalar sifatida qarash mumkin, bunda i-molxona xi koordinatada joylashgan.

Mirzakarimboyvachcha mollarini bozorga olib chiqmoqchi, shuning uchun ularni ichidan yaxshilarini tanlab olishi lozim. Bunda u barcha mollarini bir yerga to’plashi lozim. Ammo u dangasaligi tufayli, ko’p masofa yurgisi kelmayapti, shuning uchun molxonalardan tanlangan joygacha bo’lgan masofalar yig’indisi minimal bo’lishini xohlayapti. Bunda esa u sizning yordamingizga muhtoj.

Boshqacha qilib aytganda, shunaqangi k nuqtani topingki, har bir i-molxonadan k nuqtagacha bo’lgan masofalar yig’indisi minimal bo’lsin. Agar shartni qanoatlantiruvchi nuqtalar ko’p bo’lsa, ular ichida eng kichigini tanlang.


Kiruvchi ma'lumotlar:

Birinchi qatorda molxonalar sonini ifodalovchi butun N soni(1 ≤ N ≤ 2×105 ). Keyingi qatorda esa N ta butun son, molxonalar koordinatalari beriladi (0 ≤ xi ≤ 109).


Chiquvchi ma'lumotlar:

Bitta butun son – masala javobi.


Misollar
# input.txt output.txt
1
4
3 1 7 2
2
Izoh:

Birinchi test masala shartidagi rasmda keltirilgan