#include <bits/stdc++.h>
using namespace std;
int countm[200002];
int main() {
  int n, i;
  int m[100001];
  cin >> n;
  for (i = 0; i < n; i++) cin >> m[i];
  for (i = 0; i < n; i++) countm[m[i]]++;
  int low = 0, high = 20002;
  int tmp = 0;
  long long ans = 0;
  while (low < high - 1) {
    while (countm[low] == 0) low++;
    while (countm[high] == 0) high--;
    if (low < high - 1) {
      if (countm[low] == countm[high]) {
        tmp = countm[low];
        low++;
        high--;
        countm[low] += tmp;
        countm[high] += tmp;
      } else if (countm[low] < countm[high]) {
        tmp = countm[low];
        low++;
        countm[low] += tmp;
        countm[high - 1] += tmp;
        countm[high] -= tmp;
      } else {
        tmp = countm[high];
        high--;
        countm[low + 1] += tmp;
        countm[low] -= tmp;
        countm[high] += tmp;
      }
      ans += tmp;
    }
  }
  cout << ans;
  return 0;
}
