#include <fstream>
#include <iostream>
using namespace std;

ifstream in("algsort.in");
ofstream out("algsort.out");

template <typename T>
class BinaryTreeNode
{
public:
    /** CONSTRUCTOR/DESTRUCTOR METHODS **/

    //ctor - initialization with T data and null children
    BinaryTreeNode(const T& data) : m_data(data), m_parent(NULL), m_left(NULL), m_right(NULL)
    {

    }

    //dtor - unlinks the node from its left/right children and its parent
    virtual ~BinaryTreeNode()
    {
        unlinkAll();
    }

    /** LINK/UNLINK METHODS **/

    //make both children = null
    void unlinkAll()
    {
        unlinkParent();
        unlinkLeft();
        unlinkRight();
    }

    //make the parent of the node = null
    void unlinkParent()
    {
        setParent(NULL);
    }

    //make left child = null
    void unlinkLeft()
    {
        setLeft(NULL);
    }

    //make right child = null
    void unlinkRight()
    {
        setRight(NULL);
    }

    /** SET METHODS **/

    //change node's parent
    void setParent(BinaryTreeNode<T>* parent)
    {
        m_parent = parent;
    }

    //change left child
    void setLeft(BinaryTreeNode<T>* left)
    {
        m_left = left;

        if (left)
            left->setParent(this);
    }

    //change right child
    void setRight(BinaryTreeNode<T>* right)
    {
        m_right = right;

        if (right)
            right->setParent(this);
    }

    //change the T data of the node
    void setData(const T& data)
    {
        m_data = data;
    }

    /** GET METHODS **/

    //returns pointer to parent node
    virtual BinaryTreeNode<T>* getParent() const
    {
        return m_parent;
    }

    //returns pointer to left child
    virtual BinaryTreeNode<T>* getLeft() const
    {
        return m_left;
    }

    //returns pointer to right child
    virtual BinaryTreeNode<T>* getRight() const
    {
        return m_right;
    }

    //returns data of current node
    T getData() const
    {
        return m_data;
    }

    //returns number of children
    int getChildren() const
    {
        int children = 0;

        if (getLeft())
            children++;

        if (getRight())
            children++;

        return children;
    }

    /** BOOL METHODS **/

    //checks whether this node is the left child of `node`
    bool isLeftChildOf(BinaryTreeNode<T>* node)
    {
        if (!node || node->getLeft() != this)
            return false;

        return true;
    }

    //checks whether this node is the right child of `node`
    bool isRightChildOf(BinaryTreeNode<T>* node)
    {
        if (!node || node->getRight() != this)
            return false;

        return true;
    }

protected:
    //the data which current node contains (information)
    T m_data;
    //pointer to node's parent
    BinaryTreeNode<T>* m_parent;
    //pointer to left child
    BinaryTreeNode<T>* m_left;
    //pointer to right child
    BinaryTreeNode<T>* m_right;
};

template<typename T>
class AvlTreeNode : public BinaryTreeNode<T>
{
public:
    /** CONSTRUCTOR/DESTRUCTOR METHODS **/

    //ctor - calls parent's ctor and does initialization
    AvlTreeNode(const T& data) : BinaryTreeNode<T>(data), m_balanceFactor('=')
    {

    }

    //dtor - prevents compiler from generating default dtor
    ~AvlTreeNode()
    {

    }

    /** GET METHODS **/

    //returns pointer to parent node
    AvlTreeNode<T>* getParent() const override
    {
        return static_cast<AvlTreeNode<T>*>(this->m_parent);
    }

    //returns pointer to left child
    AvlTreeNode<T>* getLeft() const override
    {
        return static_cast<AvlTreeNode<T>*>(this->m_left);
    }

    //returns pointer to right child
    AvlTreeNode<T>* getRight() const override
    {
        return static_cast<AvlTreeNode<T>*>(this->m_right);
    }

    //returns the balance of this node
    char getBalance() const
    {
        return m_balanceFactor;
    }

    /** SET METHODS **/

    //subtree rooted in this node has deepened in left
    void setLeftBalance()
    {
        m_balanceFactor = 'L';
    }

    //balance was established
    void setEqualBalance()
    {
        m_balanceFactor = '=';
    }

    //subtree deepens in right
    void setRightBalance()
    {
        m_balanceFactor = 'R';
    }

private:
    //balance for the subtree rooted in this node
    char m_balanceFactor;
};

template<typename T>
class BinarySearchTree
{
public:
    /** CONSTRUCTOR/DESTRUCTOR METHODS **/

    //ctor - initializes tree's root to null
    BinarySearchTree() : m_root(NULL)
    {

    }

    //dtor - does memory management by removing all the nodes
    virtual ~BinarySearchTree()
    {
        removeAll(getRoot());
        m_root = NULL;
    }

    /** TREE TRAVERSALS METHODS **/

    //prints values in sorted order
    void inorderPrint(BinaryTreeNode<T>* root)
    {
        if (root)
        {
            inorderPrint(root->getLeft());
            out << root->getData() << " ";
            inorderPrint(root->getRight());
        }
    }

    /** SUCC/PRED METHODS **/

    //returns next element from `data` in sorted order. runs in O(h) due to call to search
    T successor(const T& data)
    {
        BinaryTreeNode<T>* node = successorNode(search(data));
        if (node)
            return node->getData();

        return false;
    }

    //returns prev element from `data` in sorted order. runs in O(h) due to call to search
    T predecessor(const T& data)
    {
        BinaryTreeNode<T>* node = predecessorNode(search(data));
        if (node)
            return node->getData();

        return false;
    }

    /** MIN/MAX METHODS **/

    //returns maximum of the BST
    T max()
    {
        return (maxNode(getRoot()))->getData();
    }

    //returns minimum of the BST
    T min()
    {
        return (minNode(getRoot()))->getData();
    }

    /** GET METHODS **/

    //returns pointer to root of the BST
    virtual BinaryTreeNode<T>* getRoot() const
    {
        return m_root;
    }

    /** BOOL METHODS **/

    //checks whether the tree is empty
    bool isEmpty() const
    {
        return getRoot() == NULL;
    }

    //checks whether a certain value exists in the BST. runs in O(h)
    bool isInserted(const T& data) const
    {
        return search(data) != NULL;
    }

    /** ADD/REMOVE METHODS **/

    //inserts a new element in the BST. runs in O(h)
    virtual void insert(const T& data)
    {
        BinaryTreeNode<T>* root = getRoot();
        BinaryTreeNode<T>* node = new BinaryTreeNode<T>(data);

        if (!root)
        {
            setRoot(node);
            return;
        }

        while (root != NULL)
        {
            if (node->getData() < root->getData())
                if (root->getLeft())
                    root = root->getLeft();
                else
                {
                    root->setLeft(node);
                    break;
                }
            else
                if (root->getRight())
                    root = root->getRight();
            else
            {
                root->setRight(node);
                break;
            }
        }
    }

    //remove the node which contains `data`, if it exists. runs in O(h) due to call to search
    void remove(const T& data)
    {
        removeNode(search(data));
    }

    //bad
    void remove(BinaryTreeNode<T>* node)
    {
        removeNode(node);
    }

    //removes every node from the subtree rooted at root
    void removeAll(BinaryTreeNode<T>* root)
    {
        if (root)
        {
            removeAll(root->getLeft());
            removeAll(root->getRight());
            delete root;
        }
    }

public:
    //pointer to the root node of the BST
    BinaryTreeNode<T>* m_root;

    /** SEARCH/ADD/REMOVE AND OTHER PRIVATE METHODS **/

    //returns pointer to node which contains certain data or null if it's not found. runs in O(h)
    BinaryTreeNode<T>* search(const T& data) const
    {
        BinaryTreeNode<T>* temp = getRoot();

        while (temp && temp->getData() != data)
            if (data > temp->getData())
                temp = temp->getRight();
            else
                temp = temp->getLeft();

        return temp;
    }

    //changes the root node
    void setRoot(BinaryTreeNode<T>* root)
    {
        m_root = root;

        if (root)
            root->unlinkParent();
    }

    //swaps node and next, changing the root accordingly
    void swapNodes(BinaryTreeNode<T>* node, BinaryTreeNode<T>* next)
    {
        BinaryTreeNode<T>* parent = node->getParent();
        if (parent)
            if (node->isLeftChildOf(parent))
                parent->setLeft(next);
            else
                parent->setRight(next);
        else
            setRoot(next);
    }

    //removes a certain node from the BST
    void removeNode(BinaryTreeNode<T>* node)
    {
        if (!node)
            return;

        BinaryTreeNode<T>* next;
        switch (node->getChildren())
        {
        case 0:
            {
                next = NULL;
                break;
            }

        case 1:
            {
                if (node->getLeft())
                    next = node->getLeft();
                else
                    next = node->getRight();

                break;
            }

        case 2:
            {
                next = successorNode(node);

                if (next->isRightChildOf(node))
                    next->setLeft(node->getLeft());
                else
                {
                    next->getParent()->setLeft(next->getRight());
                    next->setLeft(node->getLeft());
                    next->setRight(node->getRight());
                }

                break;
            }
        }

        swapNodes(node, next);
        delete node;
    }

    /** MIN/MAX (OF) METHODS **/

    //returns pointer to node with minimum value in the root subtree or null if the node given already contains the minimum
    BinaryTreeNode<T>* minNode(BinaryTreeNode<T>* root)
    {
        while (root->getLeft())
            root = root->getLeft();

        return root;
    }

    //returns pointer to node with maximum value in the 'root' subtree or null if the node given already contains the maximum
    BinaryTreeNode<T>* maxNode(BinaryTreeNode<T>* root)
    {
        while (root->getRight())
            root = root->getRight();

        return root;
    }

    /** SUCCESSOR/PREDECESSOR METHODS **/

    //returns pointer to the `next` (by data value) node or null if such node does not exist
    BinaryTreeNode<T>* successorNode(BinaryTreeNode<T>* root)
    {
        if (root->getRight())
            return minNode(root->getRight());

        BinaryTreeNode<T>* parent = root->getParent();
        while (parent && root == parent->getRight())
        {
            root = parent;
            parent = parent->getParent();
        }

        return parent;
    }

    //returns pointer to the `prev` (by data value) node or null if such node does not exist
    BinaryTreeNode<T>* predecessorNode(BinaryTreeNode<T>* root)
    {
        if (root->getLeft())
            return maxNode(root->getLeft());

        BinaryTreeNode<T>* parent = root->getParent();
        while (parent && root == parent->getLeft())
        {
            root = parent;
            parent = parent->getParent();
        }

        return parent;
    }
};

template<typename T>
class AvlTree : public BinarySearchTree<T>
{
public:
    /** CONSTRUCTOR/DESTRUCTOR METHODS **/

    //ctor - calls parent ctor to do initialization
    AvlTree() : BinarySearchTree<T>()
    {

    }

    //dtor - prevents compiler from generating default dtor
    ~AvlTree()
    {

    }

    /** GET METHODS **/

    //returns pointer to root of the BST
    AvlTreeNode<T>* getRoot() const override
    {
        return static_cast<AvlTreeNode<T>*>(this->m_root);
    }

    /** ADD/REMOVE METHODS **/

    //inserts a new element in the AVL
    void insert(const T& data) override
    {
        AvlTreeNode<T>* root = getRoot();
        AvlTreeNode<T>* fuckedUp = NULL;
        AvlTreeNode<T>* node = new AvlTreeNode<T>(data);

        if (!root)
        {
            this->setRoot(node);
            return;
        }

        while (root != NULL)
        {
            if (root->getBalance() != '=')
                fuckedUp = root;

            if (node->getData() < root->getData())
                if (root->getLeft())
                    root = root->getLeft();
                else
                {
                    root->setLeft(node);
                    break;
                }
            else
                if (root->getRight())
                    root = root->getRight();
                else
                {
                    root->setRight(node);
                    break;
                }
        }

        rebalanceTree(fuckedUp, node);
    }

    //prints values in sorted order
    void inorderPrint(AvlTreeNode<T>* root)
    {
        if (root)
        {
            inorderPrint(root->getLeft());
            out << root->getData() << " ";
            inorderPrint(root->getRight());
        }
    }


private:

    void rebalanceTree(AvlTreeNode<T>* fuckedUp, AvlTreeNode<T>* node)
    {
        AvlTreeNode<T>* root = getRoot();

        //tree was perfectly balanced
        if (fuckedUp == NULL)
        {
            if (node->getData() < root->getData())
                root->setLeftBalance();
            else
                root->setRightBalance();

            updateBalanceBetween(root, node);
            return;
        }

        //was left and new goes right or vice versa => set perfect balance
        if ((fuckedUp->getBalance() == 'L' && node->getData() > fuckedUp->getData()) || (fuckedUp->getBalance() == 'R' && node->getData() < fuckedUp->getData()))
        {
            fuckedUp->setEqualBalance();
            updateBalanceBetween(fuckedUp, node);
            return;
        }

        //1. right rotation
        if (fuckedUp->getBalance() == 'L' && node->getData() < fuckedUp->getLeft()->getData())
        {
            fuckedUp->setEqualBalance();
            rotateRight(fuckedUp);
            updateBalanceBetween(fuckedUp->getParent(), node);
            return;
        }

        //2. left rotation
        if (fuckedUp->getBalance() == 'R' && node->getData() > fuckedUp->getRight()->getData())
        {
            fuckedUp->setEqualBalance();
            rotateLeft(fuckedUp);
            updateBalanceBetween(fuckedUp->getParent(), node);
            return;
        }

        //3. left left rotation
        if (fuckedUp->getBalance() == 'L' && node->getData() > fuckedUp->getLeft()->getData())
        {
            rotateLeft(fuckedUp->getLeft());
            rotateRight(fuckedUp);
            updateBalanceLR(fuckedUp, node);
            return;
        }

        //4. right right rotation
        if (fuckedUp->getBalance() == 'R' && node->getData() < fuckedUp->getRight()->getData())
        {
            rotateRight(fuckedUp->getRight());
            rotateLeft(fuckedUp);
            updateBalanceRL(fuckedUp, node);
            return;
        }
    }

    void updateBalanceBetween(AvlTreeNode<T>* from, AvlTreeNode<T>* to)
    {
        for (AvlTreeNode<T>* temp = to->getParent(); temp != from && temp != NULL; temp = temp->getParent())
            if (from->getData() < temp->getData())
                temp->setLeftBalance();
            else
                temp->setRightBalance();
    }

    void updateBalanceLR(AvlTreeNode<T>* to, AvlTreeNode<T>* from)
    {
        if (to == getRoot())
        {
            to->setEqualBalance();
            return;
        }

        if (from->getData() < to->getParent()->getData())
        {
            to->setRightBalance();
            updateBalanceBetween(to->getParent()->getLeft(), from);
            return;
        }

        to->setEqualBalance();
        to->getParent()->getLeft()->setLeftBalance();
        updateBalanceBetween(to, from);
    }

    void updateBalanceRL(AvlTreeNode<T>* to, AvlTreeNode<T>* from)
    {
        if (to == getRoot())
        {
            to->setEqualBalance();
            return;
        }

        if (from->getData() > to->getParent()->getData())
        {
            to->setLeftBalance();
            updateBalanceBetween(to->getParent()->getRight(), from);
            return;
        }

        to->setEqualBalance();
        to->getParent()->getRight()->setRightBalance();
        updateBalanceBetween(to, from);
    }

    void rotateRight(AvlTreeNode<T>* node)
    {
        AvlTreeNode<T>* temp = node->getLeft();
        node->setLeft(temp->getRight());

        if (node == getRoot())
            this->setRoot(temp);
        else
            if (node->getParent()->getLeft() == node)
                node->getParent()->setLeft(temp);
            else
                node->getParent()->setRight(temp);

        temp->setRight(node);
    }

    void rotateLeft(AvlTreeNode<T>* node)
    {
        AvlTreeNode<T>* temp = node->getRight();
            node->setRight(temp->getLeft());

        if (node == getRoot())
            this->setRoot(temp);
        else
            if (node->getParent()->getRight() == node)
                node->getParent()->setRight(temp);
            else
                node->getParent()->setLeft(temp);

        temp->setLeft(node);
    }
};



int main()
{
    BinarySearchTree<int> bst;
    int N;

    in >> N;
    for (int i = 0; i != N; ++i)
    {
        int x;
        in >> x;
        bst.insert(x);
    }

    bst.inorderPrint(bst.getRoot());

    return 0;
}