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

Коментарі

Ще немає коментарів.