파티

기말 시험이 끝난 $N$ 명의 친구들은 파티를 하기로 했다. 파티에 필요한 음식과 물품들을 사기 위해 각자 미리 돈을 사용했다. 친구들은 $1$ 번부터 $N$ 번까지 번호가 붙어 있다고 하자. 친구들 중 $i$ 번째 친구가 사용한 돈은 $M_i$원이다.

친구들의 부담을 동일하게 하기 위해 파티 후에 서로 돈을 주고 받아 사용한 금액이 같도록 하려고 한다. 금액이 정확히 나누어 떨어지지는 않을 수 있으므로, 돈을 가장 많이 사용한 친구와 가장 적게 사용한 친구의 금액 차이가 $1$인 것까지는 허용한다.

$3$ 명의 친구 A, B, C가 파티를 하였고, 각자 사용한 금액이 $6\,000$원, $3\,000$원, $1\,000$원이라고 하자. 아래 그림처럼 B가 A에게 $334$원, C가 A에게 $2\,333$원을 주면 각자 사용한 금액이 A는 $3\,333$원, B는 $3\,334$원, C는 $3\,333$원이 되어 위의 조건을 만족한다. (아래 그림에서 네모 안은 사용한 금액, 화살표 위는 전달한 금액이다. 전달 받은 금액만큼 사용한 금액이 줄어드는 것으로 생각하면 된다.)

위 <그림 1>의 경우 전달된 금액은 모두 $334 + 2\,333 = 2\,667$원이다. 아래 <그림 2>와 같이 하면 조건을 만족하면서 전달된 금액을 $2\,666$원으로 줄일 수 있다.

$N$ 명의 학생이 처음에 사용한 금액들을 입력으로 받아 조건을 만족하도록 돈을 주고 받을 때 가능한 최소의 전달된 금액을 계산하는 프로그램을 작성하라.

입력 형식

첫 줄에 친구들의 수를 나타내는 정수 $N$이 주어진다. ($2 \leq N \leq 200\,000$)

둘째 줄에 음이 아닌 정수 $M_1$, $M_2$, $\ldots$, $M_N$이 공백을 사이에 두고 주어진다. ($M_1 + M_2 + \cdots + M_N \leq 10^{15}$)

출력 형식

전달된 금액의 가능한 최솟값을 출력한다.

예제

3
6000 3000 1000

2666

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설