Есть \(n\) зданий, состоящих из блоков, и построенных в ряд. Высота \(i\)-го здания равна \(a_i\). Вы — глава строительной бригады и хотите, чтобы построенные здания выглядели как можно приятней. За один день вы можете сделать следующую операцию:
- Выбрать два индекса \(i\) и \(j\) (\(1 \leq i, j \leq n\); \(i \neq j\)) и переместить один блок со здания \(i\) на здание \(j\). Фактически, данная операция уменьшает \(a_i\) на \(1\) и увеличивает \(a_j\) на \(1\).
Вы считаете уродливостью зданий разницу между высотой самого высокого и самого низкого зданий. Формально говоря, уродство определяется как \(\max(a)-\min(a)\).
Какого минимально возможного уродства вы сможете достичь, имея в запасе неограниченное количество дней?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимально возможное уродство зданий.
Примечание
В первом наборе входных данных, уродство уже равно \(0\).
Во втором наборе, вы можете сделать одну операцию с \(i = 1\) и \(j = 3\). Высоты зданий станут равны \([2, 2, 2, 2]\) с уродством \(0\).
В третьем наборе, вы можете сделать, например, следующие три операции:
- с \(i = 3\) и \(j = 1\): высоты зданий станут равны \([2, 2, 2, 1, 5]\),
- с \(i = 5\) и \(j = 4\): высоты зданий станут равны \([2, 2, 2, 2, 4]\),
- с \(i = 5\) и \(j = 3\): высоты зданий станут равны \([2, 2, 3, 2, 3]\).
В результате уродство зданий станет равно
\(1\). Можно доказать, что это — минимально возможное уродство, достижимое для данного теста.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3
10 10 10
4
3 2 1 2
5
1 2 3 1 5
|
0
0
1
|