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

// The main method must be in a class named "Main".
class Main {
    static class Node {
        Node parent, left, right;
        int value, height;
        public Node(int value) {
            this.value = value;
            this.height = 1; 
        }
    }

    static Node Insert(Node node, int value) {
        if (node == null) {
            return new Node(value);
        } else if (value < node.value) {
            node.left = Insert(node.left, value);
            if (node.left != null) node.left.parent = node;
        } else if (value > node.value) {
            node.right = Insert(node.right, value);
            if (node.right != null) node.right.parent = node;
        }
        updateHeight(node);
        return reBalancing(node);
    }

    static Node reBalancing(Node node) {
        int balance = getBalanceFactor(node);
        if (balance > 1 && getBalanceFactor(node.left) >= 0) {
            return rotateRight(node);
        }
        
        if(balance > 1 && getBalanceFactor(node.left) < 0) {
            node.left = rotateLeft(node.left);
            return rotateRight(node);
        }

        if(balance < -1 && getBalanceFactor(node.right) >= 0) {
            node.right = rotateRight(node.right); 
            return rotateLeft(node);
        }

        if(balance < -1 && getBalanceFactor(node.right) < 0) {
            return rotateLeft(node);
        }
        
        return node;
    }

    static void updateHeight(Node node) {
        if (node != null) {
            int left_height = node.left == null? 0: node.left.height;
            int right_height = node.right == null? 0: node.right.height;
            node.height = Math.max(left_height,right_height) + 1;
        }
    }

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

        node.right = new_root.left;
        if (new_root.left != null) {
            new_root.left.parent = node;
        }

        new_root.parent = node.parent;
        if(new_root.parent != null) {
            if(new_root.parent.left == node) {
                new_root.parent.left = new_root;
            } else if (new_root.parent.right == node) {
                new_root.parent.right = new_root;
            }
        }

        new_root.left = node;
        node.parent = new_root;

        updateHeight(node);
        updateHeight(new_root);
        
        return new_root;
    }

    static Node rotateRight(Node node) {
        Node new_root = node.left;

        node.left = new_root.right;
        if(new_root.right != null) {
            new_root.right.parent = node;
        }

        new_root.parent = node.parent;
        if (new_root.parent != null) {
            if(new_root.parent.left == node) {
                new_root.parent.left = new_root;
            } else if (new_root.parent.right == node) {
                new_root.parent.right = new_root;
            }
        }

        new_root.right = node;
        node.parent = new_root;

        updateHeight(node);
        updateHeight(new_root);
        return new_root;
        
    }

    static int getBalanceFactor(Node node) {
        if (node == null) return 0;
        int left_height = node.left == null ? 0: node.left.height;
        int right_height = node.right == null ? 0 : node.right.height; 
        return left_height - right_height;
    }
    
    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);
        }
        preOrder(root);
        
    }
}