Для обработки запросов к некоторому сетевому сервису используются n серверов. Известен текущий план распределения запросов между серверами: i-ый сервер должен обработать mi запросов.
Было решено выполнить балансировку нагрузки, переназначая задания между серверами. Более формально, пусть ma — количество запросов, которые обрабатывает наиболее загруженный сервер, а mb — количество запросов, которые обрабатывает наименее загруженный сервер. Нагрузка будет считаться сбалансированной, если разность ma - mb будет минимально возможной.
За одну секунду можно переназначить один запрос. То есть, за одну секунду можно выбрать любую пару серверов, снять ровно один запрос с одного сервера и назначить этот же запрос другому серверу.
Перед вами стоит задача найти минимальное количество секунд, по истечении которых нагрузка серверов будет сбалансирована.
Выходные данные
Выведите одно целое неотрицательное число — минимальное количество секунд, по истечении которых нагрузка серверов будет сбалансирована.
Примечание
В первом тестовом примере достаточно потратить 2 секунды. В каждую секунду необходимо переназначить запрос со 2-го сервера на 1-й. После двух секунд первому серверу будет назначено 3 запроса, а второму серверу — 4.
Во втором тестовом примере нагрузка серверов уже сбалансирована.
Один из оптимальных ответов для третьего тестового примера:
- переназначить запрос с 4-го сервера на 1-й сервер (последовательность m станет равной 2 2 3 3 5);
- переназначить запрос с 5-го сервера на 1-й сервер (последовательность m станет равной 3 2 3 3 4);
- переназначить запрос с 5-го сервера на 2-й сервер (последовательность m станет равной 3 3 3 3 3).
Это один из возможных способов выполнить балансировку нагрузки серверов за 3 секунды.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
1 6
|
2
|
|
2
|
7
10 11 10 11 10 11 11
|
0
|
|
3
|
5
1 2 3 4 5
|
3
|