#include <ctime>
#include <fstream>
#include <cstdlib>

using namespace std;

struct AVL {
    int value, priority;
    AVL *left, *right;
    AVL() { left=right=NULL;}
    AVL(int _v, int _p, AVL *_left=NULL, AVL *_right=NULL) : value(_v), priority(_p), left(_left), right(_right) {}
};
inline void RotS(AVL *& p)
{
    AVL *q=p->right;

    p->right=q->left;
    q->left=p;
    p=q;
}
inline void RotR(AVL *&p)
{
    AVL *q=p->left;

    p->left=q->right;
    q->right=p;
    p=q;
}
void Add(AVL *&root, const int& v, int& p)
{
    if(NULL == root)
       root=new AVL(v, p);
    else {
            if(v > root->value)
            {
                Add(root->right, v, p);
                if(root->right->priority > p)
                    RotS(root);
            }
            else {
                    Add(root->left, v, p);
                    if(root->left->priority > p)
                        RotR(root);
                 }
         }
}
void OutputSort(AVL *&root, ostream& out)
{
    if(NULL == root)
        return;
    OutputSort(root->left, out);
    out<<root->value<<' ';
    OutputSort(root->right, out);
}
int main()
{
    AVL *root=NULL;
    int N, i, x, p;
    ifstream in("algsort.in");
    ofstream out("algsort.out");

    in>>N;
    srand(time(NULL));
    for(i=1; i <= N; ++i)
    {
        in>>x;
        p=rand()%500009+1;
        Add(root, x, p);
    }
    OutputSort(root, out);
    out<<'\n';

    return EXIT_SUCCESS;
}