#include <iostream>
#include <fstream>
using namespace std;

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

struct link {
    int val;
    link *left;
    link *right;

    link() {
        val = 0;
        left = NULL;
        right = NULL;
    }

};

int arr[500003];
link *root = new link();

void sortT(int a[], int n) {
    root->val = a[0];
    root->left = NULL;
    root->right = NULL;

    for(int i = 1; i < n; i++) {

        link *t = new link();

        while(true) {

            if(root->right == NULL && root->left == NULL) {

                if(root->val <= a[i]) {

                    t->val = a[i];
                    t->left = root;
                    t->right = NULL;
                    root->right = t;
                    root = t;
                    break;

                }

                if(root->val >= a[i]) {

                    t->val = a[i];
                    t->right = root;
                    t->left = NULL;
                    root->left = t;
                    root = t;
                    break;

                }

            }

            //cout << root->val << " " << root->left << " " << root->right << " " << a[i] << endl;

            if(root->right == NULL) {
                if(root->val <= a[i]) {
                    t->val = a[i];
                    t->left = root;
                    t->right = NULL;
                    root->right = t;
                    root = t;
                    break;
                } else {

                    if(root->left->val <= a[i]) {
                        t->val = a[i];
                        t->left = root->left;
                        t->right = root;
                        root->left->right = t;
                        root->left = t;
                        root = t;
                        break;
                    }

                    root = root->left;
                    continue;
                }
            }

            if(root->left == NULL) {

                if(root->val >= a[i]) {
                    t->val = a[i];
                    t->right = root;
                    t->left = NULL;
                    root->left = t;
                    root = t;
                    break;
                } else {

                    if(root->right->val > a[i]) {
                        t->val = a[i];
                        t->left = root;
                        t->right = root->right;
                        root->right->left = t;
                        root->right = t;
                        root = t;
                        break;
                    }

                    root = root->right;
                    continue;
                }
            }

            if(root->right->val > a[i] && root->val < a[i]) {

                t->val = a[i];
                t->left = root;
                t->right = root->right;

                root->right->left = t;
                root->right = t;
                root = t;
                break;

            }


            if(root->left->val < a[i] && root->val > a[i]) {

                t->val = a[i];
                t->left = root->left;
                t->right = root;

                root->left->right = t;
                root->left = t;
                root = t;
                break;

            }

            if(root->val > a[i]) {
                root = root->left;
            } else {
                root = root->right;
            }

        }

    }

    while(root->left != NULL) {
        root = root->left;
    }

    while(root != NULL) {

        out << root->val << " ";
        root = root->right;

    }

    //cout << root->val;

}

int main() {

    int n;
    in >> n;
    for(int i = 0; i < n; i++)
        in >> arr[i];

    sortT(arr, n);

    return 0;
}