Problem description

Dotychczas w zadaniach sparingowych poznaliśmy już Pana Janusza – prezesa Januszex S.A. oraz jego syna Jasia. W rzeczywistości okazuje się, że Pan Janusz ma N dzieci ponumerowanych kolejnymi liczbami naturalnymi od 1 do N. Zbliżają się święta, więc Pan Janusz postanowił dać dzieciom cukierki. Przygotował więc N worków z cukierkami, po jednym dla każdego dziecka. Niestety, okazało się, że worki wcale nie muszą zawierać takiej samej liczby cukierków.

Nie byłoby dobrze dać tak prezenty dzieciom – mogłyby myśleć, że Pan Janusz niektóre z nich bardziej kocha, a inne mniej. Teraz Pan Janusz musi zmarnować trochę czasu, żeby wyrównać sytuację. W jednej sekundzie Pan Janusz może wykonać jedną z dwóch rzeczy:

• zabrać z worka dowolnego dziecka jeden cukierek,
• dołożyć do worka dowolnego dziecka jeden cukierek.

Pan Janusz ma oczywiście dostatecznie dużo cukierków do dokładania, ale jak zawsze ma mało czasu – pomóż mu wyrównać liczbę cukierków we wszystkich workach tak, aby zmarnował jak najmniej czasu.

Napisz program, który: wczyta liczbę dzieci Pana Janusza i liczbę cukierków w workach, wyznaczy minimalny czas niezbędny do wyrównania sytuacji i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N, określająca liczbę dzieci Pana Janusza. W drugim (ostatnim) wierszu wejścia znajduje się ciąg N liczb naturalnych A_i, pooddzielanych pojedynczymi odstępami. Są to liczby cukierków w kolejnych workach.

Wyjście

W pierwszym i jedynym wierszu wyjścia należy wypisać jedną liczbę całkowitą – minimalny czas niezbędny do wyrównania liczby cukierków w workach.

Ograniczenia

1 ≤ N ≤ 500 000, 0 ≤ A_i ≤ 10⁹.

Przykład

3
4 8 5

4