Masala #0127

Mirzakarimboyvachchani n ta molxonasi bor. Ushbu molxonalarni Ox o’qidagi nuqtalar sifatida qarash mumkin, bunda i-molxona x_i 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×10⁵ ). Keyingi qatorda esa N ta butun son, molxonalar koordinatalari beriladi (0 ≤ x_i ≤ 10⁹).

Bitta butun son – masala javobi.