#include<iostream>
#include<fstream>
#define T 15
std::ifstream fin("algsort.in");
std::ofstream fout("algsort.out");

class BTreeNode {
private:
    BTreeNode** C;
    int* keys;
    int n;
    int t;
    bool isLeaf;
public:
    BTreeNode(int t, bool leaf);
    void insertNonFull(int k);
    void splitChild(int i, BTreeNode* y);
    void traverse();
    BTreeNode* Search(int k);
    friend class BTree;
};

class BTree {
private:
    BTreeNode* root;
    int t;
public:
    BTree(int t) : root(NULL), t(t) {}
    void traverse() {
        if(this->root != NULL)
            root->traverse();
    }

    BTreeNode* Search(int k) {
        return (root == NULL) ? NULL : root->Search(k);
    }

    void Insert(int k);
};

BTreeNode::BTreeNode(int t, bool leaf) : n(0), t(t), isLeaf(leaf) {
    keys = new int[2*t-1];
    C = new BTreeNode*[2*t];
}

void BTreeNode::traverse() {
    int i;
    for(i = 0; i < n; ++i) {
        if(!isLeaf)
            C[i]->traverse();
        fout << keys[i] << " ";
    }

    if(!isLeaf)
        C[i]->traverse();
}

BTreeNode* BTreeNode::Search(int k) {
    int i = 0;
    while(i < n && keys[i] < k)
        i++;
    if(keys[i] == k)
        return this;
    if(isLeaf)
        return NULL;
    return C[i]->Search(k);
}

void BTree::Insert(int k) {
    if(root == NULL) {
        root = new BTreeNode(t, true);
        root->keys[0] = k;
        root->n = 1;
    } else {
        if(root->n == 2*t - 1) {
            BTreeNode* s = new BTreeNode(t, false);
            s->C[0] = root;
            s->splitChild(0, root);
            int i = 0;
            if(s->keys[0] < k)
                i++;
            s->C[i]->insertNonFull(k);
            root = s;
        } else root->insertNonFull(k);
    }
}

void BTreeNode::insertNonFull(int k) {
    int i = n - 1;
    if(isLeaf) {
        while(i >= 0 && keys[i] > k) {
            keys[i + 1] = keys[i];
            i--;
        }
        keys[i + 1] = k;
        n++;
    } else {
        while(i >= 0 && keys[i] > k)
            i--;
        if(C[i + 1]->n == 2*t-1) {
            splitChild(i + 1, C[i + 1]);
            if(keys[i + 1] < k)
                i++;
        }
        C[i + 1]->insertNonFull(k);
    }
}

void BTreeNode::splitChild(int i, BTreeNode* y) {
    BTreeNode* z = new BTreeNode(y->t, y->isLeaf);
    z->n = t - 1;
    for(int j = 0; j < t - 1; j++)
        z->keys[j] = y->keys[j + t];
    if(!y->isLeaf) {
        for(int j = 0; j < t; ++j)
            z->C[j] = y->C[j + t];
    }
    y->n = t - 1;
    for(int j = n; j >= i + 1; j--)
        C[j + 1] = C[j];
    C[i + 1] = z;
    for(int j = n - 1; j >= i; j--)
        keys[j + 1] = keys[j];
    keys[i] = y->keys[t - 1];
    n++;
}

BTree r(T);

int main() {
    int n, x;
    fin >> n;
    for(int i = 0; i < n; ++i) {
        fin >> x;
        r.Insert(x);
    }
    r.traverse();
    fout << "\n";
    fin.close();
    fout.close();
    return 0;
}