C. Балансировка нагрузки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для обработки запросов к некоторому сетевому сервису используются n серверов. Известен текущий план распределения запросов между серверами: i-ый сервер должен обработать mi запросов.

Было решено выполнить балансировку нагрузки, переназначая задания между серверами. Более формально, пусть ma — количество запросов, которые обрабатывает наиболее загруженный сервер, а mb — количество запросов, которые обрабатывает наименее загруженный сервер. Нагрузка будет считаться сбалансированной, если разность ma - mb будет минимально возможной.

За одну секунду можно переназначить один запрос. То есть, за одну секунду можно выбрать любую пару серверов, снять ровно один запрос с одного сервера и назначить этот же запрос другому серверу.

Перед вами стоит задача найти минимальное количество секунд, по истечении которых нагрузка серверов будет сбалансирована.

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

В первой строке содержится целое положительное число n (1 ≤ n ≤ 105) — количество серверов.

Во второй строке содержится последовательность неотрицательных целых чисел m1, m2, ..., mn (0 ≤ mi ≤ 2·104), где mi — количество запросов, изначально предназначенных для обработки i-м сервером.

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

Выведите одно целое неотрицательное число — минимальное количество секунд, по истечении которых нагрузка серверов будет сбалансирована.

Примеры
Входные данные
2
1 6
Выходные данные
2
Входные данные
7
10 11 10 11 10 11 11
Выходные данные
0
Входные данные
5
1 2 3 4 5
Выходные данные
3
Примечание

В первом тестовом примере достаточно потратить 2 секунды. В каждую секунду необходимо переназначить запрос со 2-го сервера на 1-й. После двух секунд первому серверу будет назначено 3 запроса, а второму серверу — 4.

Во втором тестовом примере нагрузка серверов уже сбалансирована.

Один из оптимальных ответов для третьего тестового примера:

  1. переназначить запрос с 4-го сервера на 1-й сервер (последовательность m станет равной 2 2 3 3 5);
  2. переназначить запрос с 5-го сервера на 1-й сервер (последовательность m станет равной 3 2 3 3 4);
  3. переназначить запрос с 5-го сервера на 2-й сервер (последовательность m станет равной 3 3 3 3 3).

Это один из возможных способов выполнить балансировку нагрузки серверов за 3 секунды.