Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Balancer

time limit per test

0.5 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputPetya has *k* matches, placed in *n* matchboxes lying in a line from left to right. We know that *k* is divisible by *n*. Petya wants all boxes to have the same number of matches inside. For that, he can move a match from its box to the adjacent one in one move. How many such moves does he need to achieve the desired configuration?

Input

The first line contains integer *n* (1 ≤ *n* ≤ 50000). The second line contains *n* non-negative numbers that do not exceed 10^{9}, the *i*-th written number is the number of matches in the *i*-th matchbox. It is guaranteed that the total number of matches is divisible by *n*.

Output

Print the total minimum number of moves.

Examples

Input

6

1 6 2 5 3 7

Output

12

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/19/2018 07:29:12 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|