#include <bits/stdc++.h>

using namespace std;

template<typename T>
class Node {
  public:
    Node(const int value=int(), T* l=nullptr, T* r=nullptr) : value_(value), son_{l, r} {}
    T*& get(size_t dir) { return son_[dir]; }
    const T* get(size_t dir) const { return son_[dir]; }
    int& value() { return value_; }
    int value() const { return value_; }
  private:
    int value_;
    T* son_[2];
};

class AvlNode : public Node<AvlNode> {  // CRTP
  public:
    AvlNode() : Node(0, this, this), height_(0) {}
    AvlNode(const int value, AvlNode* l=NIL, AvlNode* r=NIL) : Node(value, l, r) { refresh(); }

    int height() const { return height_; }
    
    void refresh() {
        height_ = 1;
        for (size_t dir : {0, 1}) {
            if (get(dir) != nullptr and height_ >= get(dir)->height()) {
                height_ = get(dir)->height_ + 1;
            }
        }
    }

    void rotate(size_t dir) {
        {
            AvlNode* new_sons[2] = {get(0), get(1)};
            new_sons[dir] = new_sons[dir]->get(1 - dir);
            get(1 - dir) = new AvlNode(value(), new_sons[0], new_sons[1]);
        }
        value() = get(dir)->value();
        get(dir) = get(dir)->get(dir);
        refresh();
    }

    friend ostream& operator <<(ostream& os, const AvlNode& rhs) {
        if (rhs.height() == 0) {
            return os;            
        }
        os << *rhs.get(0);
        if (rhs.get(0)->height() != 0) {
            os << ' ';
        }
        os << rhs.value();
        if (rhs.get(1)->height() != 0) {
            os << ' ';
        }
        os << *rhs.get(1);
        return os;
    }

    static AvlNode* NIL;
  private:
    int height_;
};

AvlNode* AvlNode::NIL = new AvlNode();

class AvlTree {
  public:
    AvlTree() : root_(AvlNode::NIL) {}

    void Insert(const int value) {
        Add(root_, value);
    }

    friend ostream& operator <<(ostream& os, const AvlTree& rhs) {
        return os << *rhs.root_;
    }

  private:
    void Add(AvlNode*& node, const int value, const int depth=0) {
        if (node == AvlNode::NIL) {
            node = new AvlNode(value);
            return;
        }
        
        assert(depth <= 100);

        const size_t dir = (value > node->value());
        Add(node->get(dir), value, depth+1);
        if (node->get(dir)->height() > node->get(1 - dir)->height() + 1) {
            if (node->get(dir)->get(1 - dir)->height() > node->get(dir)->get(dir)->height()) {
                node->get(dir)->rotate(1 - dir);
            }

            node->rotate(dir);
        }

        node->refresh();
    }

    AvlNode* root_;
};

int main() {
    #ifdef INFOARENA
    ifstream cin("algsort.in");
    ofstream cout("algsort.out");
    #endif
    
    AvlTree tree;
    int n; cin >> n;
    for (int i = 0; i < n; ++i) {
        int x; cin >> x;
        tree.Insert(x);
    }
    
    cout << tree << endl;
    
    return 0;
}