//#include <iostream>
//#include <vector>
#include <fstream>

//#include <set>

//#include <algorithm>

#include <random>
#include <limits>
#include <functional>
/*
#include <ctime>
#include <cstdio>
#include <cstdlib>
*/
//using namespace std;
std::ifstream in("grader_test13.in");
std::ofstream out("algsort.out");

using my_engine = std::default_random_engine; // type of engine
using my_distribution = std::uniform_int_distribution<>; // type of distribution
my_engine re {}; // the default engine
my_distribution one_to_maxint {1,std::numeric_limits<int>::max()}; // distribution that maps to the ints 1..6
auto die = std::bind(one_to_maxint,re); // make a generator

class Treap
{


    int infinity = 1010101010;
    struct node
    {
        int key;
        int priority;
        node * left, *right;
        node(int x,int pr,node * lt,node *rt):key{x},priority{pr},left{lt},right{rt}{};
    };
    node * root ,*nil;
    void init()
    {
        root = nil = new node(0, 0, nullptr, nullptr);
    }
    void rotateRight(node* &t)
    {
        node * l = t->left;
        t->left = l->right;
        l->right = t;
        t = l;
    }
    void rotateLeft(node* &t)
    {
        node* r = t->right;
        t->right = r->left;
        r->left = t;
        t = r;
    }
    void balance(node* &t)
    {
        if(t->left->priority>t->priority)
            rotateRight(t);
        else if(t->right->priority > t->priority)
            rotateLeft(t);
    }
    bool search(int x,node* &t)
    {
        if(t == nil)
            return false;
        else if( x < t->key)
            return search(x,t->left);
        else if(x > t->key)
            return search(x,t->right);
        else
            return true;
    }
    void insert(int x, node* &t)
    {
        if(t == nil)
        {
            t = new node(x,/*rand()+1*/die(),nil,nil);
            return;
        }
        if(x <=t->key)
            insert(x,t->left);
        else if(x > t->key)
            insert(x,t->right);
        balance(t);
    }
    void remove(int x,node* &t)
    {
        if(t == nil)
            return;
        else if(x < t->key)
            remove(x,t->left);
        else if(x > t->key)
            remove(x,t->right);
        else
        {
            if(t->right == nil && t->left == nil)
                delete t, t = nil;
            else
            {
                /*if(t->left == nil)
                    t = t->right;
                else if(t->right == nil)
                    t = t->left;
                else
                {*/
                    if(t->left->priority > t->right->priority)
                        rotateRight(t);
                    else
                        rotateLeft(t);
                    remove(x,t);
                //}
            }
        }
    }
    void split(node* &R, node* &Ts, node* &Tg, int key)
    {
        insert(key,R);
        Ts = R->left, Tg = R->right;
        delete R, R = nil;
    }
    void join(node* &R,node* &Ts,node* &Tg, int key)
    {
        R = new node(key,0,Ts,Tg);
        remove(key,R);
    }
public:
    Treap()
    {
        //srand(unsigned(time(0)));
        init();
    }
    void insert(int x)
    {
        insert(x,root);
    }
    void erase(int x)
    {
        //if(search(x,root))
        remove(x,root);
    }
    bool find(int x)
    {
        return search(x,root);
    }
    void srd(node* &t)
    {
        if(t!= nil)
        {
            srd(t->left);
            out<<t->key<<" ";
            srd(t->right);
        }
    }
    void showSorted()
    {
        srd(root);
    }
};

int main()
{


    //int x = die();
    //BST bst;
    //AVL avl;
    Treap treap;
    //set<int> um;

    int n,x,op,nr,nr2,j=0;
    in >> n;
    for(int i = 0  ; i< n ; i++)
    {
        //in >> op >> x;
        in >>x;
        /*switch(op)
        {
            case 1:
                treap.insert(x);
                //avl.insert(x);
                //bst.insert(x);
                  //  um.insert(x);
               break;
            case 2:
                treap.erase(x);
                //um.erase(x);
                //bst.erase(x);
                //avl.remove(x);
             break;
            case 3:
                nr = treap.find(x);
                //nr = avl.find(x);
                //nr = bst.find(x);
            //nr2 = (um.find(x)!=um.end())?1:0;
            out<<nr<<'\n';
            //ing>> nr2;
            //j++;
            //if(nr != nr2)
              //  cout<<"linia "<<j<<" "<<nr<<"!="<<nr2<<"elementul "<<x<<'\n';
            break;
        }*/
        treap.insert(x);
        //bst.insert(x);
    }

    treap.showSorted();
    //bst.showSorted();z
}