440_B. Balancer_17194
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?

Input

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.

Output

Print the total minimum number of moves.

Examples

Input

6
1 6 2 5 3 7


Output

12
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
import java.util.*;
import java.io.*;
/**
 *
 * @author Cookies
 */
public class Class1 {
    
    @SuppressWarnings("empty-statement")
    public static void main(String[] args)throws IOException{
    
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] b = br.readLine().split(" ");
        long n = gl(b[0]);
        String[] v = br.readLine().split(" ");
        long[] arr = new long[v.length];
        long sum = 0;
        for(int i =0; i< n; i++){
            
            arr[i] = gl(v[i]);
            sum = sum+arr[i];
        }
        
        long div = sum/n;
        long count=0;
        for(int i = 0; i< n; i++){
            
        if(arr[i]> div){
        arr[i+1] = arr[i+1]+ arr[i]-div;
        count = count+ arr[i]-div;
        }
        if(arr[i]< div){
        arr[i+1]= arr[i+1] - (div-arr[i]);
        count = count + (div-arr[i]);
            
        }
        }
        System.out.println(count);
    }
    
    public static int gi(String a){
    
    return Integer.parseInt(a);
    
    }
    
    public static long gl(String a){
    
    return Long.parseLong(a);
    
    }
}
