#include <bits/stdc++.h>

using namespace std;

class Reader {
 public:
    Reader() = delete;
    Reader(const Reader&) = delete;
    Reader& operator=(const Reader&) = delete;

    Reader(Reader&&) = default;
    Reader& operator=(Reader&&) = default;
    ~Reader() = default;
    
    explicit Reader(istream& input_stream) : input_stream_(input_stream), 
        idx_(kBuffSize), buffer_(new char[kBuffSize]) { }
    
    Reader& operator >>(char str[]) { ReadCString(str); return *this; }
    Reader& operator >>(string& str) { ReadString(str); return *this; }
    Reader& operator >>(char& ch) { ch = SkipSpaces(); return *this; }
    
    template<class F>
    typename enable_if<is_floating_point<F>::value,
        Reader&>::type operator >>(F& x) { ReadFloat(x); return *this; }

    template<class I>
    typename enable_if<is_integral<I>::value,
        Reader&>::type operator >>(I& x) { ReadInteger(x); return *this; }
  private:
    static constexpr int kBuffSize = 1 << 12;

    char GetChar() {
        if (idx_ == kBuffSize) {
            input_stream_.read(buffer_.get(), kBuffSize);
            idx_ = 0;
        }
        return buffer_[idx_++];
    }

    char SkipSpaces() {
        char c;
        do {
            c = GetChar(); 
        } while (isspace(c));
        return c;
    }
    
    void ReadString(string& x) {
        char c = SkipSpaces();
        x.clear();
        do {
            x.push_back(c);
            c = GetChar();
        } while (not isspace(c));
    }

    void ReadCString(char str[]) {
        char c = SkipSpaces();
        char* pointer = str;
        do {
            *(pointer++) = c;
            c = GetChar();
        } while (not isspace(c));
        *pointer = 0;
    }

    template<class S> 
    typename enable_if<is_signed<S>::value,
    void>::type ReadInteger(S& x) {
        char c = SkipSpaces();
        bool minus;
        if (c == '-') {
            minus = true;
            c = GetChar();
        } else {
            minus = false;
        }

        x = 0;
        do {
            x = x * 10 + c - '0';
            c = GetChar();
        } while (isdigit(c));
        if (minus) {
            x = -x;
        }
    }
    
    template<typename U>
    typename enable_if<is_unsigned<U>::value,
    void>::type ReadInteger(U& x) {
       char c = SkipSpaces();
       x = 0;
       do {
           x = x * 10 + c - '0';
           c = GetChar();
       } while (isdigit(c));
    }

    template<typename F>
    void ReadFloat(F& x) {
        string buffer; ReadString(buffer);
        istringstream is(buffer);
        is >> x;
    }
    
    istream& input_stream_;
    int idx_;
    unique_ptr<char[]> buffer_;
};

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) {
        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)->rotate(1 - dir);
            }

            node->rotate(dir);
        }

        node->refresh();
    }

    AvlNode* root_;
};

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