#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <stdlib.h>
#include <cassert>
using namespace std;

class AVL {
    private:
        struct node {
            int key, h;
            // int t_nodes; // left + right child nodes + 1
            node *l, *r;
        };

        node *R, *NIL;


        void _set(node *n) {
            n->h = 1 + max(n->r->h, n->l->h);
            // n->t_nodes = 1 + n->r->t_nodes + n->l->t_nodes;
        }

        node* _rotright(node *n) {
            node *t = n->l;
            n->l = t->r;
            t->r = n;
            _set(n);
            _set(t); return t;
        }

        node* _rotleft(node *n) {
            node *t = n->r;
            n->r = t->l;
            t->l = n;
            _set(n);
            _set(t);
            return t;
        }

        node* _balance(node* n) {
            _set(n);
            if (n->r->h > n->l->h + 1) {
                if (n->r->l->h > n->r->r->h)
                    n->r = _rotright(n->r);
                n = _rotleft(n);
            }
            else if (n->l->h > n->r->h + 1) {
                if (n->l->r->h > n->l->l->h + 1)
                    n->l = _rotleft(n->l);
                n = _rotright(n);
            }
            return n;
        }

        node* _insert(node *n, int key) {
            if (n == NIL) {
                n = (node *) malloc(sizeof(node));
                n->key = key;
                n->h = 1;
                n->l = n->r = NIL;
                // n->t_nodes = 1;
                return n;
            }
            if (n->key < key)
                n->r = _insert(n->r, key);
            else
                n->l = _insert(n->l, key);
            return _balance(n);
        }

        node* _erase(node *n, int key) {
            node *t;
            if (n == NIL) return n;
            if (n->key == key) {
                if (n->l == NIL || n->r == NIL){
                    t = (n->l == NIL ? n->r : n->l);
                    free(n);
                    return t;
                }
                else {
                    for (t = n->r; t->l != NIL; t = t->l);
                    n->key = t->key;
                    n->r = _erase(n->r, t->key);
                }
            }
            else if (n->key < key)
                n->r = _erase(n->r, key);
            else
                n->l = _erase(n->l, key);
            return _balance(n);
        }

        int _search(node *n, int key) {
            if (n == NIL) return 0;
            if (n->key == key) return 1;
            if (n->key < key)
                return _search(n->r, key);
            return _search(n->l, key);
        }

        // node* _get_nth(node *n, int nth) {
        //     if (n->l->t_nodes + 1 == nth)
        //         return n;
        //     else if (n->l->t_nodes >= nth)
        //         return _get_nth(n->l, nth);
        //     else
        //         return _get_nth(n->r, nth - n->l->t_nodes - 1);
        // }

        void _inorder_traversal(node *n) {
            if (n == NIL)
                return;
            _inorder_traversal(n->l);
            printf("%d ", n->key);
            _inorder_traversal(n->r);
        }

        void _clear(node *n) {
            if (n == NIL)
                return;
            _clear(n->l);
            _clear(n->r);
            free(n);
        }

    public:
        AVL() {
            R = NIL = (node *) malloc(sizeof(node));
            NIL->key = NIL->h = 0;
            // Nil->t_nodes = 0;
            NIL->l = NIL->r = NULL;
        }

        ~AVL() {
            _clear(R);
            free(NIL);
        }

        void Insert(int key) {
            R = _insert(R, key);
        }

        void Erase(int key) {
            R = _erase(R, key);
        }

        int Search(int key) {
            return _search(R, key);
        }

        // int GetNth(int nth) {
        //     assert(1 <= nth && nth <= R->t_nodes); 
        //     return _get_nth(R, nth)->key;
        // }

        void InorderTraversal() {
            _inorder_traversal(R);
            printf("\n");
        }
};

int main() {
    freopen("avl.in", "r", stdin);
    freopen("avl.out", "w", stdout);
    int n;
    int x;
    scanf("%d", &n);
    AVL a1;
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &x);
        a1.Insert(x);
    }
    a1.InorderTraversal();
    
    return 0;
}