#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]; }
    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 + max(get(0)->height(), get(1)->height()); }

    AvlNode* rotate(size_t dir) {
        AvlNode* y = get(dir);
        if (y == NIL) {
            return this;
        }
        
        get(dir) = y->get(1 - dir);
        y->get(1 - dir) = this;
        refresh();
        y->refresh();
        return y;
    }

    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) {
        if (node == AvlNode::NIL) {
            node = new AvlNode(value);
            return;
        }

        const size_t dir = (value > node->value());
        Add(node->get(dir), value);
        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) = node->get(dir)->rotate(1 - dir);
            }

            node = 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;
}