12140. Трохи зрівняти
Відправити розв'язок
Бали:
100
Time limit:
2.0s
Memory limit:
500M
Authors:
Problem type
Allowed languages
C++, Java, Pascal, Python
Вам дано цілу послідовність \(A=(A_1 , A_2 ,…, A_N )\). Ви можете виконати наступну операцію будь-яку кількість разів (можливо, нуль).
- Виберіть цілі числа \(i\) та \(j\), щоб \(1≤i,j≤N\). Зменшіть \(A_i\) на одиницю та збільшіть \(A_j\) на одиницю.
Знайдіть мінімальну кількість операцій, необхідну для того, щоб різниця між мінімальним і максимальним значеннями \(A\) становила не більше одного.
Обмеження
- \(1≤N≤2×10^5\)
- \(1≤A_i ≤10^9\)
- Усі вхідні значення є цілими числами.
Формат вхідних даних
Перший рядок містить ціле число \(N\).
Наступний рядок містить цілі числа \(A_i\).
Формат вихідних даних
У вихідний потік виведіть відповідь.
Приклад вхідних даних
4
4 7 3 7
Приклад вихідних даних
3
За допомогою наступних трьох операцій різниця між мінімальним і максимальним значеннями \(A\) стає щонайбільше одиницею.
- Виберіть \(i=2\) і \(j=3\), щоб отримати \(A=(4,6,4,7)\).
- Виберіть \(i=4\) і \(j=1\), щоб отримати \(A=(5,6,4,6)\).
- Виберіть \(i=4\) і \(j=3\), щоб отримати \(A=(5,6,5,5)\).
Ви не можете зробити різницю між максимальним і мінімальним значенням \(A\) щонайбільше на одиницю за трьома операціями, тому відповідь 3.
Приклад вхідних даних
1
313
Приклад вихідних даних
0
Приклад вхідних даних
10
999999997 999999999 4 3 2 4 999999990 8 999999991 999999993
Приклад вихідних даних
2499999974
Коментарі