Բարձրությունները հավասարեցնել
Ծախսերը օպտիմալացնելու նպատակով քաղաքի ճարտարապետական բաժինը դիմել է ձեզ, որպեսզի օգնեք բոլոր շենքերը նույն բարձրության դարձնել։ Բոլոր շենքերի միանման բարձրությունը զգալիորեն կնվազեցնի շինարարական ծախսերը:
Քաղաքում նախապես ընտրված են
n շենքեր, որոնց բարձրությունները տարբերվում են։ Եթե որոշ շենքի բարձրություն փոխենք x-ով, ապա այդ փոփոխությունը կհանգեցնի x րոպե տևողությամբ հանդիպման։ Քանի որ դուք զբաղված եք, ցանկանում եք հնարավորինս կրճատել հանդիպումների վրա ծախսվող ընդհանուր ժամանակը։ Ո՞րն է հանդիպումների վրա ծախսվող նվազագույն ժամանակը, եթե բոլոր շենքերը պիտի ունենան նույն բարձրությունը։Մուտք
Մուտքի առաջին տողում տրվում է մեկ ամբողջ թիվ
n (1 ≤ n ≤ ):Հաջորդ տողում տրված են
n բացատով բաժանված ամբողջ թվեր (1 ≤ ≤ ), որոնք ներկայացնում են շենքերի սկզբնական բարձրությունները։Ելք
Ծրագիրը պետք է տպի մեկ ամբողջ թիվ. հանդիպումների վրա ծախսվող նվազագույն հնարավոր ժամանակը։
Օրինակներ
Մուտք | Ելք |
5
1 4 8 2 9 | 14 |
Բացատրություն
Լավագույն ընտրությունը բարձրությունը 4 դարձնելն է։ Այդ դեպքում մեզ պետք է փոխել 1 → 4 (3 րոպե), 2 → 4 (2 րոպե), 8 → 4 (4 րոպե), 9 → 4 (5 րոպե) ⇒ ընդհանուր 14 րոպե։
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB