#include <stdio.h>
#include <stdlib.h>
 
typedef struct node {
    int val;
    struct node *next;
} Node;
 
Node *head = NULL;
 
Node* createN(int x){
    Node *newnode;
    newnode = (Node *)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}
 
void initL(int n){
    int x, i;
    Node *p;
    scanf("%d", &x);
    head = createN(x);
    p = head;
    for(i = 1; i < n; i++){
        scanf("%d", &x);
        p->next = createN(x);
        p = p->next;
    }
}
 
void freeL(){
    Node *p;
    while(head != NULL){
        p = head->next;
        free(head);
        head = p;
    }
}
 
void printN(Node *a){
    if(a == NULL) printf("NULL\n");
    else printf("%d\n", a->val);
}
 
void printL(){
    Node *p = head;
    while(p != NULL){
        printf("%d ", p->val);
        p = p->next;
    }
    printf("\n");
}
 
Node* getN(int n){
    int i;
    Node *p;
    p = head;
    for(i = 1; i < n; i++) p = p->next;
    return p;
}
 
int countL(){
    int ret = 0;
    Node *p = head;
    while(p != NULL){
        p = p->next;
        ret++;
    }
    return ret;
}
 
Node* searchX(int x){
    Node *p;
    for(p = head; p != NULL; p = p->next){
        if(p->val == x) break;
    }
    return p;
}
 
void insHead(int x){
    Node *p;        //１
    p = createN(x); //１
    p->next = head; //２
    head = p;       //３
}
 
void insMiddle(int n, int x){
    int i;
    Node *p, *q;
    p = head;           //１
    for(i = 1; i < n; i++){   //２
        p = p->next;    //２
    }
    q = createN(x);     //３
    q->next = p->next;  //４
    p->next = q;        //５
}
 
void insTail(int x){
    Node *p;
    p = head;               //１
    if(p == NULL){
        head = createN(x);
        return;
    }
    while(p->next != NULL){ //２
        p = p->next;        //２
    }
    p->next = createN(x);   //３
}
 
void delHead(){
    Node *p;
    p = head;           //１
    head = head->next;  //２
    free(p);            //３
}
 
void delMiddle(int n){
    int i;
    Node *p, *q;
    p = head;           //１
    for(i = 1; i < n - 1; i++){ //２
        p = p->next;    //２
    }
    q = p->next;        //３
    p->next = q->next;  //４
    free(q);            //５
}
 
void delTail(){
    Node *p;
    p = head;                       //１
    while(p->next->next != NULL){   //２
        p = p->next;                //２
    }
    free(p->next);                  //３
    p->next = NULL;                 //４
}
 
void makeL(int n, int a[]){
    int i;
    for(i = 0; i < n; i++) {
        int x = a[i];
 
 
        if (head == NULL || x < head->val) {
            insHead(x);
        } 
 
        else {
            Node *p = head;
            while (p->next != NULL && p->next->val < x) {
                p = p->next;
            }
            Node *q = createN(x);
            q->next = p->next;
            p->next = q;
        }
    }
}
 
int main(void){
    int i, n;
    int *a;
    scanf("%d", &n);
    a = (int*)malloc(sizeof(int) * n);
    for(i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    makeL(n, a);
    printL();
    freeL();
    free(a); 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KCnR5cGVkZWYgc3RydWN0IG5vZGUgewogICAgaW50IHZhbDsKICAgIHN0cnVjdCBub2RlICpuZXh0Owp9IE5vZGU7CgpOb2RlICpoZWFkID0gTlVMTDsKCk5vZGUqIGNyZWF0ZU4oaW50IHgpewogICAgTm9kZSAqbmV3bm9kZTsKICAgIG5ld25vZGUgPSAoTm9kZSAqKW1hbGxvYyhzaXplb2YoTm9kZSkpOwogICAgbmV3bm9kZS0+dmFsID0geDsKICAgIG5ld25vZGUtPm5leHQgPSBOVUxMOwogICAgcmV0dXJuIG5ld25vZGU7Cn0KCnZvaWQgaW5pdEwoaW50IG4pewogICAgaW50IHgsIGk7CiAgICBOb2RlICpwOwogICAgc2NhbmYoIiVkIiwgJngpOwogICAgaGVhZCA9IGNyZWF0ZU4oeCk7CiAgICBwID0gaGVhZDsKICAgIGZvcihpID0gMTsgaSA8IG47IGkrKyl7CiAgICAgICAgc2NhbmYoIiVkIiwgJngpOwogICAgICAgIHAtPm5leHQgPSBjcmVhdGVOKHgpOwogICAgICAgIHAgPSBwLT5uZXh0OwogICAgfQp9Cgp2b2lkIGZyZWVMKCl7CiAgICBOb2RlICpwOwogICAgd2hpbGUoaGVhZCAhPSBOVUxMKXsKICAgICAgICBwID0gaGVhZC0+bmV4dDsKICAgICAgICBmcmVlKGhlYWQpOwogICAgICAgIGhlYWQgPSBwOwogICAgfQp9Cgp2b2lkIHByaW50TihOb2RlICphKXsKICAgIGlmKGEgPT0gTlVMTCkgcHJpbnRmKCJOVUxMXG4iKTsKICAgIGVsc2UgcHJpbnRmKCIlZFxuIiwgYS0+dmFsKTsKfQoKdm9pZCBwcmludEwoKXsKICAgIE5vZGUgKnAgPSBoZWFkOwogICAgd2hpbGUocCAhPSBOVUxMKXsKICAgICAgICBwcmludGYoIiVkICIsIHAtPnZhbCk7CiAgICAgICAgcCA9IHAtPm5leHQ7CiAgICB9CiAgICBwcmludGYoIlxuIik7Cn0KCk5vZGUqIGdldE4oaW50IG4pewogICAgaW50IGk7CiAgICBOb2RlICpwOwogICAgcCA9IGhlYWQ7CiAgICBmb3IoaSA9IDE7IGkgPCBuOyBpKyspIHAgPSBwLT5uZXh0OwogICAgcmV0dXJuIHA7Cn0KCmludCBjb3VudEwoKXsKICAgIGludCByZXQgPSAwOwogICAgTm9kZSAqcCA9IGhlYWQ7CiAgICB3aGlsZShwICE9IE5VTEwpewogICAgICAgIHAgPSBwLT5uZXh0OwogICAgICAgIHJldCsrOwogICAgfQogICAgcmV0dXJuIHJldDsKfQoKTm9kZSogc2VhcmNoWChpbnQgeCl7CiAgICBOb2RlICpwOwogICAgZm9yKHAgPSBoZWFkOyBwICE9IE5VTEw7IHAgPSBwLT5uZXh0KXsKICAgICAgICBpZihwLT52YWwgPT0geCkgYnJlYWs7CiAgICB9CiAgICByZXR1cm4gcDsKfQoKdm9pZCBpbnNIZWFkKGludCB4KXsKICAgIE5vZGUgKnA7ICAgICAgICAvL++8kQogICAgcCA9IGNyZWF0ZU4oeCk7IC8v77yRCiAgICBwLT5uZXh0ID0gaGVhZDsgLy/vvJIKICAgIGhlYWQgPSBwOyAgICAgICAvL++8kwp9Cgp2b2lkIGluc01pZGRsZShpbnQgbiwgaW50IHgpewogICAgaW50IGk7CiAgICBOb2RlICpwLCAqcTsKICAgIHAgPSBoZWFkOyAgICAgICAgICAgLy/vvJEKICAgIGZvcihpID0gMTsgaSA8IG47IGkrKyl7ICAgLy/vvJIKICAgICAgICBwID0gcC0+bmV4dDsgICAgLy/vvJIKICAgIH0KICAgIHEgPSBjcmVhdGVOKHgpOyAgICAgLy/vvJMKICAgIHEtPm5leHQgPSBwLT5uZXh0OyAgLy/vvJQKICAgIHAtPm5leHQgPSBxOyAgICAgICAgLy/vvJUKfQoKdm9pZCBpbnNUYWlsKGludCB4KXsKICAgIE5vZGUgKnA7CiAgICBwID0gaGVhZDsgICAgICAgICAgICAgICAvL++8kQogICAgaWYocCA9PSBOVUxMKXsKICAgICAgICBoZWFkID0gY3JlYXRlTih4KTsKICAgICAgICByZXR1cm47CiAgICB9CiAgICB3aGlsZShwLT5uZXh0ICE9IE5VTEwpeyAvL++8kgogICAgICAgIHAgPSBwLT5uZXh0OyAgICAgICAgLy/vvJIKICAgIH0KICAgIHAtPm5leHQgPSBjcmVhdGVOKHgpOyAgIC8v77yTCn0KCnZvaWQgZGVsSGVhZCgpewogICAgTm9kZSAqcDsKICAgIHAgPSBoZWFkOyAgICAgICAgICAgLy/vvJEKICAgIGhlYWQgPSBoZWFkLT5uZXh0OyAgLy/vvJIKICAgIGZyZWUocCk7ICAgICAgICAgICAgLy/vvJMKfQoKdm9pZCBkZWxNaWRkbGUoaW50IG4pewogICAgaW50IGk7CiAgICBOb2RlICpwLCAqcTsKICAgIHAgPSBoZWFkOyAgICAgICAgICAgLy/vvJEKICAgIGZvcihpID0gMTsgaSA8IG4gLSAxOyBpKyspeyAvL++8kgogICAgICAgIHAgPSBwLT5uZXh0OyAgICAvL++8kgogICAgfQogICAgcSA9IHAtPm5leHQ7ICAgICAgICAvL++8kwogICAgcC0+bmV4dCA9IHEtPm5leHQ7ICAvL++8lAogICAgZnJlZShxKTsgICAgICAgICAgICAvL++8lQp9Cgp2b2lkIGRlbFRhaWwoKXsKICAgIE5vZGUgKnA7CiAgICBwID0gaGVhZDsgICAgICAgICAgICAgICAgICAgICAgIC8v77yRCiAgICB3aGlsZShwLT5uZXh0LT5uZXh0ICE9IE5VTEwpeyAgIC8v77ySCiAgICAgICAgcCA9IHAtPm5leHQ7ICAgICAgICAgICAgICAgIC8v77ySCiAgICB9CiAgICBmcmVlKHAtPm5leHQpOyAgICAgICAgICAgICAgICAgIC8v77yTCiAgICBwLT5uZXh0ID0gTlVMTDsgICAgICAgICAgICAgICAgIC8v77yUCn0KCnZvaWQgbWFrZUwoaW50IG4sIGludCBhW10pewogICAgaW50IGk7CiAgICBmb3IoaSA9IDA7IGkgPCBuOyBpKyspIHsKICAgICAgICBpbnQgeCA9IGFbaV07CiAgICAgICAgCiAgICAgICAKICAgICAgICBpZiAoaGVhZCA9PSBOVUxMIHx8IHggPCBoZWFkLT52YWwpIHsKICAgICAgICAgICAgaW5zSGVhZCh4KTsKICAgICAgICB9IAogICAgICAgIAogICAgICAgIGVsc2UgewogICAgICAgICAgICBOb2RlICpwID0gaGVhZDsKICAgICAgICAgICAgd2hpbGUgKHAtPm5leHQgIT0gTlVMTCAmJiBwLT5uZXh0LT52YWwgPCB4KSB7CiAgICAgICAgICAgICAgICBwID0gcC0+bmV4dDsKICAgICAgICAgICAgfQogICAgICAgICAgICBOb2RlICpxID0gY3JlYXRlTih4KTsKICAgICAgICAgICAgcS0+bmV4dCA9IHAtPm5leHQ7CiAgICAgICAgICAgIHAtPm5leHQgPSBxOwogICAgICAgIH0KICAgIH0KfQoKaW50IG1haW4odm9pZCl7CiAgICBpbnQgaSwgbjsKICAgIGludCAqYTsKICAgIHNjYW5mKCIlZCIsICZuKTsKICAgIGEgPSAoaW50KiltYWxsb2Moc2l6ZW9mKGludCkgKiBuKTsKICAgIGZvcihpID0gMDsgaSA8IG47IGkrKyl7CiAgICAgICAgc2NhbmYoIiVkIiwgJmFbaV0pOwogICAgfQogICAgbWFrZUwobiwgYSk7CiAgICBwcmludEwoKTsKICAgIGZyZWVMKCk7CiAgICBmcmVlKGEpOyAKICAgIHJldHVybiAwOwp9