eolymp
Задачи

Кубики

Кубики

На День народження свого племінника Петрика Степан подарував йому набір кубиків. Петрик тут же став будувати з кубиків паркан, однак стовпчики у Петрика виходили різної висоти. Степана зацікавило питання: "Яку найменшу кількість перекладань можна зробити, щоб висота будь-яких двох стовпчиків відрізнялась не більше ніж на один кубик. Крім того за один раз можна перекладати тільки один кубик з довільного стовпчика на поруч розташований.

Вхідні дані

У першому рядку вхідного файлу записано число N (1 ≤ N ≤ 1000) – кількість стовпчиків з кубиками у Петрика. Другий рядок містить N цілих чисел – висоту кожного стовпчика (у кубиках). Усі числа не перевищують 106.

Вихідні дані

У вихідний файл необхідно вивести одне єдине число – найменшу кількість перекладань кубиків, в результаті яких висота будь-яких двох стовпчиків не буде відрізнятися більш ніж на один кубик.

Пояснення до прикладу.

Зробити два перекладання зі стовпчика №3 у стовпчик №4. Результат – 3 4 6 4 5. Потім перекласти кубик зі стовпчика №2 у стовпчик №1. Результат – 4 3 6 4 5. І на останок перекласти кубик зі стовпчика №3 у стовпчик №2. Результат – 4 4 5 4 5.

Лимит времени 1 секунда
Лимит использования памяти 64 MiB
Входные данные #1
5
3 4 8 2 5
Выходные данные #1
4
Источник ACM-ICPC Ukraine 2016, Перший етап Україна, 16 квітня 2016 року