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

class Main {
    static class Node {
        Node parent;
        int value;
        Node left;
        Node right;
        public Node(int value) {
            this.value = value;
            this.parent = null;
            this.left = null;
            this.right = null;
        }
    }

    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);
                node.left.parent = node;
            } else if (value > node.value) {
                node.right = Insert(node.right, value);
                node.right.parent = node;
            } 
        }
        return node;
    }
    
    static Node Search(Node node, int value) {
        if (node == null || node.value == value) {
            return node;
        }
        if (value < node.value) return Search(node.left, value);
        else return Search(node.right, value);
       
    }
    

    static Node rightRotation(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 if (node.parent.right == node) {
            node.parent.right = newRoot;
            newRoot.parent = node.parent;
        }

        newRoot.right = node;
        node.parent = newRoot;
        return root;
    }
    
    static Node leftRotation(Node root, Node p) {
        Node new_p = p.right;
        
        p.right = new_p.left;
        if(new_p.left != null) new_p.left.parent = p;

        if (p.parent == null) root = new_p;
        else if (p.parent.left == p) {
            p.parent.left = new_p;
            new_p.parent = p.parent;
            }
        else if(p.parent.right == p) {
            p.parent.right = new_p;
            new_p.parent = p.parent;
        }

        new_p.left = p; 
        p.parent = new_p;
        return root;
    }

    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);
        }

        if (root.left == null || root.right == null) {
            if (root.left == null && root.right.left == null) root = leftRotation(root, root);
            else if (root.left == null && root.right.left != null) {
                root = rightRotation(root, root.right);
                root = leftRotation(root, root);
            } else if (root.right == null && root.left.right != null) {
                root = leftRotation(root, root.left);
                root = rightRotation(root, root);
            } else if (root.right == null) root = rightRotation(root,root);
        }

        preOrder(root);
    }
}