EduBrick
← вернуться к уроку · Жадные идеи и их ловушки

Сделать всех равными

5000 мс · 256 МБ · всё или ничего

Дан список из nn чисел. За один ход можно увеличить или уменьшить любое число на единицу.

За какое наименьшее число ходов можно сделать все числа равными?

Формат ввода

В первой строке число nn от 11 до 21052 \cdot 10^5. Во второй — nn чисел от 109-10^9 до 10910^9.

Формат вывода

Одно число.

Примеры

ввод
3
1 2 3
вывод
2

Примечание

Подумайте, что происходит с суммой расстояний, если сдвинуть цель на единицу вправо: она уменьшается на число элементов справа и растёт на число элементов слева.

Войдите, чтобы отправлять решения.
← Вернуться к уроку