#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;
struct treap_node
{
    int key, priority;
    treap_node *left, *right;
    treap_node(int key, int priority, treap_node* left, treap_node* right)
    {
        this->key = key;
        this->priority = priority;
        this->left = left;
        this->right = right;
    }
}*root, *NIL;

void treap_init()
{
    srand(time(0));

    root = NIL = new treap_node(0,0,0,0);
}

void treap_rotate_left(treap_node* &node)
{
    treap_node* aux = node->left;
    node->left = aux->right;
    aux->right = node;
    node = aux;
}

void treap_rotate_right(treap_node* &node)
{
    treap_node* aux = node->right;
    node->right = aux->left;
    aux->left = node;
    node = aux;
}

void treap_balance(treap_node* &node)
{
    if(node->left->priority  > node->priority)
        treap_rotate_left(node);
    else if(node->right->priority > node->priority)
        treap_rotate_right(node);
}

void treap_insert(treap_node* &node, int key, int priority)
{
    if(node == NIL)
    {
        node = new treap_node(key,priority,NIL,NIL);
        return;
    }
    if(key < node->key)
        treap_insert(node->left, key, priority);
    else if(key > node->key)
        treap_insert(node->right, key, priority);

    treap_balance(node);
}

void treap_inorder(treap_node *node)
{
    if(node != NIL)
    {
        treap_inorder(node->left);
        printf("%d ",node->key);
        treap_inorder(node->right);
    }
}

int nr;

int main()
{
    freopen("algsort.in","r",stdin);
    freopen("algsort.out","w",stdout);

    treap_init();
    scanf("%d",&nr);
    for(int i=1;i<=nr;i++)
    {
        int x;
        scanf("%d",&x);
        treap_insert(root,x,rand()+1);
    }
    treap_inorder(root);

    return 0;
}