Training Site
Sideways banner

Accounting Woes

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 255 megabytes
Time limit: 1.0 seconds

You have been given the role of treasurer in the prestigious Natural Zillionaire's Iceboat Cabal (NZIC). In this role, you oversee N distinct branches of the Cabal, each of which has spent some amount of money this year to promote iceboats.

If the N branches don't have the same total expense over the year, an internal fight might break out. Hence, you have been secretly tasked with manipulating the records to balance the expenses across the branches.

To ensure the total expenditure of the entire Cabal remains the same, you are allowed to subtract some integer amount from the expense of a branch and add it to the expense another branch as many times as necessary. If it is not possible to perfectly balance across the branches, you may ask some of the branches to spend more, but this amount should be minimised. You need to report the total extra spending necessary.


The first line contains a single integer, N (2 \le N \le 100).

The second line contains N space-separated integers between 0 and 1000 (inclusive), each representing the expense of one branch of the Cabal.


Print a single integer - the minimum total extra spending needed to ensure the expenses across the branches balance.


For 50% of the marks, N = 2


In sample case 1, we have three branches which have expended 10, 2, and 4 dollars. One optimal way to balance the branches is to subtract 4 from the first branch and add it to the second branch to get 6 6 4. Then we ask the third branch to spend 2 dollars more - getting a perfect balance of 6 6 6. So overall, the total extra spending is 2.

  • Sample Input 1

    10 2 4

    Sample Output 1