#include<stdio.h>
#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<time.h>
using namespace std;

struct T {
    int key, priority;
    T *left, *right;
    T() {}
    T(int key, int priority, T* left, T* right) {
        this->key = key;
        this->priority = priority;
        this->left = left, this->right = right;
    }
} *R, *nil; // nil indica un nod 'gol'

void init(T* &R) {
    srand(unsigned(time(0)));
    R = nil = new T(0, 0, NULL, NULL);
}

void parc(T* n){
    if(n== nil)
        return;
    parc(n->left);
    printf("%d ",n->key);
    parc(n->right);
}

int search(T* n, int key) {
    if (n == nil) return 0;
    if (key == n->key) return 1;
    if (key < n->key)
        return search(n->left, key);
    else
        return search(n->right, key);
}

void rotleft(T* &n) {
    T *t = n->left;
    n->left = t->right, t->right = n;
    n = t;
}

void rotright(T* &n) {
    T *t = n->right;
    n->right = t->left, t->left = n;
    n = t;
}

void balance(T* &n) {
    if (n->left->priority > n->priority)
        rotleft(n);
    else if (n->right->priority > n->priority)
        rotright(n);
}

void insert(T* &n, int key, int priority) {
    if (n == nil) {
        n = new T(key, priority, nil, nil);
        return;
    }
    if (key <= n->key)
        insert(n->left, key, priority);
    else if (key > n->key)
        insert(n->right, key, priority);

    balance(n);
}

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

init(R);
int N,x;
cin>>N;


for(int i=1;i<=N;++i){
    cin>>x;
    insert(R,x,rand()%100000);
}

parc(R);

return 0;
}