Приведение высот к одному уровню
Чтобы оптимизировать расходы, городской проектный отдел обратился к вам с просьбой сделать высоту всех зданий одинаковой. Если все здания будут одинаковой высоты, это значительно снизит затраты на строительство.
В городе подготовлено
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