Vitoning oilasi

Vito bitta uzun ko'chaga ko'chib o'tmoqchi. Shu ko'chada uning $n$ ta qarindoshi yashaydi, $i$-qarindoshining uyi $s_i$ raqamli. Ikki uy orasidagi masofa — raqamlari ayirmasining moduli.

Vito har kuni barcha qarindoshlarini ziyorat qiladi, shuning uchun u o'z uyidan barcha qarindoshlarigacha bo'lgan masofalar yig'indisi eng kichik bo'ladigan uyni tanlamoqchi (uy raqami istalgan butun son bo'lishi mumkin). Shu eng kichik yig'indini toping.

Birinchi qatorda $n$ ($1 \le n \le 10^5$). Ikkinchi qatorda $n$ ta butun son $s_1, \ldots, s_n$ ($0 \le s_i \le 10^9$). Bir uyda bir nechta qarindosh yashashi mumkin.

Bitta son — masofalarning eng kichik yig'indisi.

Yig'indi $|s_1 - x| + \ldots + |s_n - x|$ ni $x$ = median (saralangan massivning o'rtadagi elementi) minimallashtiradi: $x$ medianadan chapda bo'lsa, uni o'ngga surish yig'indini kamaytiradi, o'ngda bo'lsa — aksincha. $n$ juft bo'lsa, ikki o'rta element orasidagi istalgan $x$ mos keladi. Birinchi misolda $x = 4$, javob $2 + 0 + 2 = 4$.

Yig'indi $5 \cdot 10^{13}$ gacha yetadi — 64 bitli tur kerak.

Manba: UVa 10041.