class

#include<bits/stdc++.h>
using namespace std;

class List_Node
{
    public:

    int info;
    List_Node *next, *prev;

    List_Node(int data)
    {
        this->info = data;
        this->next = this->prev = this;
    }
    ~List_Node()
    {
        delete this;
    }
};

class List
{
    List_Node *start, *finish;

    public:

    void push_back_element(int data)
    {
        if(start == NULL)
        {
            start = finish = new List_Node(data);
            return;
        }

        List_Node *tmp = new List_Node(data);
        tmp->next = start;
        tmp->prev = finish;
        start->prev = tmp;
        finish->next = tmp;
        finish = tmp;
    }

    void insert_element_after(List_Node* &tmp, int data)
    {
        List_Node *aux = new List_Node(data);
        if(tmp == finish)
        {
            aux->next = tmp->next;
            aux->prev = tmp;
            tmp->next->prev = aux;
            tmp->next = aux;
            finish = aux;
        }
        else
        {
            aux->next = tmp->next;
            aux->prev = tmp;
            tmp->next->prev = aux;
            tmp->next = aux;
        }
    }

    void insert_element_before(List_Node* &tmp, int data)
    {
        List_Node *aux = new List_Node(data);
        if(tmp == start)
        {
            aux->next = tmp;
            aux->prev = tmp->prev;
            tmp->prev->next = aux;
            tmp->prev = aux;
            start = aux;
        }
        else
        {
            aux->next = tmp;
            aux->prev = tmp->prev;
            tmp->prev->next = aux;
            tmp->prev = aux;
        }
    }

    List_Node* search_element(int data)
    {
        List_Node *tmp = start;
        do
        {
            if(tmp->info == data)
                return tmp;
            tmp = tmp->next;
        }
        while(tmp != start);

        return NULL;
    }

    List_Node* search_specific_element(int data)
    {
        List_Node *tmp = start;
        do
        {
            if(tmp->info >= data)
                return tmp;
            tmp = tmp->next;
        }
        while(tmp != start);

        return NULL;
    }

    void delete_element(List_Node* &tmp)
    {
        if(tmp == start)
        {
            tmp->next->prev = finish;
            finish->next = tmp->next;
            start = tmp->next;
        }
        else if(tmp == finish)
        {
            tmp->prev->next = start;
            start->prev = tmp->prev;
            finish = tmp->prev;
        }
        else
        {
            tmp->next->prev = tmp->prev;
            tmp->prev->next = tmp->next;
        }

        delete tmp;
    }

    void sort_list()
    {
        List_Node *tmp1 = start;
        do
        {
            List_Node *tmp2 = tmp1->next;
            do
            {
                if(tmp1->info > tmp2->info)
                    swap(tmp1->info, tmp2->info);
                tmp2 = tmp2->next;
            }
            while(tmp2 != start);
            tmp1 = tmp1->next;
        }
        while(tmp1 != finish);
    }

    void stable_insertion_element(int data)
    {
        if(start == NULL)
        {
            start = finish = new List_Node(data);
            return;
        }

        //List_Node *tmp = new List_Node(data);
        if(data <= start->info)
        {
            insert_element_before(start, data);
        }
        else if(data >= finish->info)
        {
            insert_element_after(finish, data);
        }
        else
        {
            List_Node *tmp = search_specific_element(data);
            insert_element_before(tmp, data);
        }
    }

    void display()
    {
        List_Node *tmp = start;

        if(start)
            do
            {
                cout<< tmp->info <<" ";
                tmp = tmp->next;
            }
            while(tmp != start);
    }

    ~List()
    {
        List_Node *tmp = start;
        do
        {
            List_Node *aux = tmp->next;
            delete_element(tmp);
            tmp = aux;
        }
        while(tmp != start);
        delete start;
        cout<< "\nList was deleted!\n";
    }

};

int n, x;

int main()
{
    List *s = new List();
    cin>> n;
    for(int i = 1; i <= n; i++)
        cin>> x, s->stable_insertion_element(x);
    s->display();

    return 0;
}