import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    
    static class Node {
        Node parent, left, right;
        int value, height;
        public Node(int value) {
            this.value = value;
            this.height = 1; // Node같은 경우 생성값 설정 안하면 null인가? 그럼 height도 딱히 적지 않고 0에서부터 시작하면 안되나?
        }
    }

    static Node lastInsertedNode;

    
    static Node Insert(Node node, int value) {
        
        if (node == null) {
            Node newNode = new Node(value);
            lastInsertedNode = newNode;
            return newNode;
        }
        if (value < node.value) {
            node.left = Insert(node.left, value);
            node.left.parent = node;
        }
        if (value > node.value) {
            node.right = Insert(node.right, value);
            node.right.parent = node;
        }
        return node;
    }

    // 자식 노드를 통해 높이를 찾는다.
    static void updateHeight(Node node) {
        if (node != null) {
            int leftHeight = node.left != null? node.left.height : 0;
            int rightHeight = node.right != null? node.right.height : 0;
            node.height = Math.max(leftHeight, rightHeight) + 1;
        }
        
    }

    static int getBalanceFactor(Node node) {
        if (node == null) return 0;
        int leftHeight = node.left != null? node.left.height : 0;
        int rightHeight = node.right != null? node.right.height : 0;
        return leftHeight - rightHeight;
    }

    static Node rotateLeft(Node node) {
        Node newRoot = node.right; 

        node.right = newRoot.left;
        if(newRoot.left != null) newRoot.left.parent = node;

        if(node.parent == null) root = newRoot; 
        else {
            if(node.parent.left == node) {
                node.parent.left = newRoot;
                newRoot.parent = node.parent;
            } else {
                node.parent.right = newRoot;
                newRoot.parent = node.parent;
            }
        }

        newRoot.left = node;
        node.parent = newRoot;

        updateHeight(node);
        updateHeight(newRoot);
        
        return newRoot;
    }

    static Node rotateRight(Node root, Node node) {
        Node newRoot = node.left; 
        
        node.left = newRoot.right;
        if(newRoot.right != null) newRoot.right.parent = node;

        if(node.parent == null) root = newRoot;
        else {
           if(node.parent.left == node) {
               node.parent.left = newRoot;
               newRoot.parent = node.parent;
           }  else {
               // 근데 이게 else라고 단언할 수 있나... 맞긴 한데 좀 불안한데
               node.parent.right = newRoot;
               newRoot.parent = node.parent;
           }
        }
        newRoot.right = node; 
        node.parent = newRoot;
        
        updateHeight(node);
        updateHeight(newRoot);
        
        return newRoot;
    }

    static Node rebalancing(Node root, Node node) {
        Node cur = node;
        while (cur != null) {
            updateHeight(cur);
            int bf = getBalanceFactor(cur);
            Node new_subRoot = cur;
            // LL
            if (bf > 1 && getBalanceFactor(cur.left) >= 0) {// 여기 왼쪽 자식의 bf는 1이상이여야 하는거아님? 아 어짜피 해봤자 1이려나 1인지 확인하는게 정확한 로직 아닐까?
                new_subRoot = rotateRight(root, cur);
            } // LR
            else if (bf > 1 && getBalanceFactor(cur.left) < 0) { //1인지 -1인지를 여기서 0기준으로 양수,음수냐를 쓴거구나.
                cur.left = rotateLeft(root, cur.left);
                new_subRoot = rotateRight(root, cur);
            } // RL
            else if (bf < -1 && getBalanceFactor(cur.right) >= 0) {
                cur.right = rotateRight(root,cur.right);
                new_subRoot = rotateLeft(root,cur);
            } // RR
            else if (bf < -1 && getBalanceFactor(cur.right) < 0) {
                new_subRoot = rotateLeft(root,cur);
            }
        }
        if (cur.parent == null) root = new_subRoot;
        else {
            if(cur.parent.left == cur) {
                cur.parent.left = new_subRoot;
                // new_subRoot.parent = cur.parent; 부모는 설정 안해도 되나...?
            } else {
                cur.parent.right = new_subRoot;
            }
            
        cur = new_subRoot.parent;
        }
        return node;
    }

    static void preOrder(Node node) {
        if (node == null) return;
        System.out.println(node.value);
        preOrder(node.left);
        preOrder(node.right);
    }
    
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        Node root = null;
        for (int i=0; i<N; i++) {
            int t = Integer.parseInt(st.nextToken());
            root = Insert(root, t);
            root = rebalancing(root, lastInsertedNode);
        }

        preOrder(root);
        
    }
}