Кубики

На день рождения своего племянника Петрика, Степан подарил ему набор кубиков. Петрик сразу же начал строить из них забор, но столбики у него получались разной высоты. Степан задался вопросом: "Какое минимальное количество перекладываний нужно сделать, чтобы высота любых двух столбиков отличалась не более чем на один кубик?" При этом за один раз можно переместить только один кубик с одного столбика на соседний.

Входные данные

В первой строке входного файла указано число N (1 ≤ N ≤ 1000) — количество столбиков с кубиками у Петрика. Во второй строке содержится N целых чисел — высота каждого столбика (в кубиках). Все числа не превышают 10^6.

Выходные данные

В выходной файл необходимо вывести одно число — минимальное количество перекладываний кубиков, после которых высота любых двух столбиков будет отличаться не более чем на один кубик.

Примеры

Примечание

Сначала сделайте два перекладывания со столбика №3 в столбик №4. Результат — 3 4 6 4 5. Затем переместите кубик со столбика №2 в столбик №1. Результат — 4 3 6 4 5. И, наконец, переместите кубик со столбика №3 в столбик №2. Результат — 4 4 5 4 5.