Matches – for children?

Petya has N·k (1 ≤ N ≤ 15000) matches, distributed across N boxes arranged in a row. Petya wants each box to contain the same number of matches. To achieve this, he can move a match to an adjacent box. How many such operations will it take to reach the desired configuration?

Input

The first line contains the integer N. The second line contains N integers, each not exceeding 10^9, representing the number of matches in each box (the first number corresponds to the first box, the second to the second box, and so on).

Output

Output the minimum number of operations needed to achieve the desired configuration.

Examples