440B.md (913B)
1 Source: https://codeforces.com/problemset/problem/440/B 2 3 B. Balancer 4 5 time limit per test 6 7 0.5 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 stdin 16 17 output 18 19 stdout 20 21 Petya 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? 22 23 Input 24 25 The first line contains integer *n* (1 ≤ *n* ≤ 50000). The second line contains *n* non-negative numbers that do not exceed 109, 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*. 26 27 Output 28 29 Print the total minimum number of moves. 30 31 Examples 32 33 Input 34 35 ``` 36 6 37 1 6 2 5 3 7 38 ``` 39 40 Output 41 42 ``` 43 12 44 ```