//https://www.hackerrank.com/contests/w1/challenges/bst-maintenance
import java.io.*;
import java.util.*;
 
public class Solution{
    public static void main(String[] args) throws IOException {
        StringBuffer sb = new StringBuffer();
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int[] A = new int[N];
        
        N = 0;
        for(String a : br.readLine().split(" ")){
            A[N++] = Integer.parseInt(a);
        }
        
        Tree tree = new Tree();
        for(int a : A){
            tree.add(a);
            sb.append(tree.getDistance() + "\n");
        }
        
        System.out.print(sb);
    }
    public static class Tree{
        //The root of the tree
        private Node root;
        //The sum of distances from each node to every other node
        private long treeDistance;
        
        public Tree(){
            this.root = null;
            this.treeDistance = 0L;
        }
        
        public void add(int value){
            //Hold path from direct parent to root node
            List<Node> parents = new ArrayList<Node>();
            //Hold siblings at each depth from same depth to depth 1
            List<Node> siblings = new ArrayList<Node>();
            
            //Add the new value
            this.root = add(this.root, value, parents, siblings);
            
            //For each depth
            int size = parents.size();
            for(int i = 0; i < size; ++i){
                Node parent = parents.get(i);
                Node sibling = siblings.get(i);
                int depth = i+1;
                
                //Update parent distance with distance to node
                parent.distance += depth;
                
                //Update tree distance with:
                //    Distance from node to parent
                //    Distance from node to sibling * the number of nodes in sibling subtree
                //    Sum of distance from sibling node to every subnode
                this.treeDistance += sibling == null ? depth : depth + ((long)(depth+1))*sibling.size + sibling.distance;
            }
        }
        
        private Node add(Node node, int value, List<Node> parents, List<Node> siblings){
            if (node == null){
                return new Node(value);
            }
            
            if (value < node.value){
                node.left = add(node.left, value, parents, siblings);
                siblings.add(node.right);
            } else {
                node.right = add(node.right, value, parents, siblings);
                siblings.add(node.left);
            }
            
            node.size++;
            parents.add(node);
            
            return node;
        }
        
        public long getDistance(){
            return this.treeDistance;
        }
        
        private class Node{
            //Nodes less than value
            public Node left;
            //Nodes greater than value
            public Node right;
            //The size of the subtree, including itself
            public int size;
            //The value for this node
            public int value;
            //The sum of distances from this node to all nodes in subtree 
            public long distance;
            
            public Node(int value){
                this.value = value;
                this.left = null;
                this.right = null;
                this.size = 1;
                this.distance = 0L;
            }
        }
    }
}
@@ -1083,176 +1083,229 @@
     
-//Hold path from direct parent to root node%0A            List%3CNode%3E parents = new ArrayList%3CNode%3E();%0A            //Hold siblings at each depth from same depth to depth 1
+%0A            //Insert node if empty%0A            if (this.root == null)%7B%0A                this.root = new Node(value);%0A                return;%0A            %7D%0A            %0A            //Hold path from root node to parent node
 %0A   
@@ -1324,23 +1324,22 @@
 t%3CNode%3E 
-sibling
+parent
 s = new 
@@ -1388,309 +1388,845 @@
   //
-Add the new value%0A            this.root = add(this.root, value, parents, siblings);%0A            %0A            //For each depth%0A            int size = parents.size();%0A            for(int i = 0; i %3C size; ++i)%7B%0A                Node parent = parents.get(i);%0A                Node sibling = siblings.get(i);
+Find where to place the node%0A            Node node = this.root;%0A            do %7B%0A                %0A                node.size++;%0A                parents.add(node);%0A                %0A                if (value %3C node.value)%7B%0A                    if (node.left == null)%7B%0A                        node = node.left = new Node(value);%0A                        break;%0A                    %7D%0A                    node = node.left;%0A                %7D else %7B%0A                    if (node.right == null)%7B%0A                        node = node.right = new Node(value);%0A                        break;%0A                    %7D%0A                    node = node.right;%0A                %7D%0A                %0A            %7D while (true);%0A            %0A            //From parent node to root%0A            int depth = 0;%0A            for(int i = parents.size() - 1; i %3E= 0; --i)%7B
 %0A   
@@ -2242,23 +2242,36 @@
     
-int depth = i+1
+Node parent = parents.get(i)
 ;%0A  
@@ -2383,16 +2383,18 @@
 ance += 
+++
 depth;%0A 
@@ -2508,60 +2508,8 @@
 rent
-%0A                //    Distance from node to sibling
  * t
@@ -2601,28 +2601,14 @@
 ing 
-node to every subnod
+subtre
 e%0A  
@@ -2645,50 +2645,16 @@
 e +=
- sibling == null ? depth : depth +
  ((long)
 (dep
@@ -2653,675 +2653,186 @@
 ong)
-(
 depth
-+1))*sibling.size + sibling.distance;%0A            %7D%0A        %7D%0A        %0A        private Node add(Node node, int value, List%3CNode%3E parents, List%3CNode%3E siblings)%7B%0A            if (node == null)%7B%0A                return new Node(value);%0A            %7D%0A            %0A            if (value %3C node.value)%7B%0A                node.left = add(node.left, value, parents, siblings);%0A                siblings.add(node.right);%0A            %7D else %7B%0A                node.right = add(node.right, value, parents, siblings);%0A                siblings.add(node.left);%0A            %7D%0A            %0A            node.size++;%0A            parents.add(node);%0A            %0A            return node;
+)*(parent.size - node.size) + (parent.distance - node.distance - node.size);%0A                %0A                //Move up the tree%0A                node = parent;%0A            %7D
 %0A   

Update bst-maintenance solution for first weekly contest; Change recursive add to loop, Change treeDistance formula from using parent and sibling to just parent