Masala #0127
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.
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).
Bitta butun son – masala javobi.
# | input.txt | output.txt |
---|---|---|
1 |
4 3 1 7 2 |
2 |
Birinchi test masala shartidagi rasmda keltirilgan