#include <iostream>
#include <fstream>

using namespace std;

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

int n;

struct AVL {
    int value;
    int height;
    AVL *left;
    AVL *right;

    AVL(int value) {
        this->value = value;
        this->left = NULL;
        this->right = NULL;
        this->height = 0;
    };
};

AVL *T;

int get_height(AVL *T) {
    if (T == NULL) return -1;
    else return T->height;
}

AVL *rotate_left(AVL *&T) {
    AVL *T2 = new AVL(0);

    T2 = T->left;
    T->left = T2->right;
    T2->right = T;

    T->height = max(get_height(T->left), get_height(T->right)) + 1;
    T2->height = max(get_height(T2->left), get_height(T)) + 1;

    return T2;
}

AVL *rotate_right(AVL *&T) {
    AVL *T2;

    T2 = T->right;
    T->right = T2->left;
    T2->left = T;

    T->height = max(get_height(T->left), get_height(T->right)) + 1;
    T2->height = max(get_height(T), get_height(T2->right)) + 1;

    return T2;
}

void insert_node(int value, AVL *&T) {
    //cout << value << endl;
    if (T == NULL) {
        T = new AVL(value);
        return;
    }
    if (value <= T->value) {
        insert_node(value, T->left);
        if (get_height(T->left) - get_height(T->right) == 2) {
            if (value <= T->left->value)
                T = rotate_left(T);
            else {
                T->left = rotate_right(T->left);
                T = rotate_left(T);
            }
        }
    }
    else {
        insert_node(value, T->right);
        if (get_height(T->right) - get_height(T->left) == 2) {
            if (value > T->right->value)
                T = rotate_right(T);
            else {
                T->right = rotate_left(T->right);
                T = rotate_right(T);
            }
        }
    }
}

void scrie(AVL *T) {
    if (T == NULL) return;
    scrie(T->left);
    g << T->value << ' ';
    scrie(T->right);
}

void citeste() {
    f >> n;

    int x;
    for (int i = 1; i <= n; i++) {
        f >> x;
        insert_node(x, T);
    }
}

int main() {
    citeste();
    scrie(T);

    return 0;
}