#include<cstdio>
using namespace std;
int ;

struct Treap
{
    int val,pr;
    Treap *lf,*rt;
    Treap(){}
    Treap(int val, int pr, int *lf, int *rt)
    {
        this->val=val;
        this->pr=pr;
        this->lf=lf;
        this->rt=rt;
    }
}*R,*nil;

void rot_right(int *&nod)
{
    Treap *aux=nod->rt;
    nod->rt = aux->lf; aux->lf = nod;
    nod=aux;
}

void rot_left(int *&nod)
{
    Treap *aux=nod->lf;
    nod->lf = aux->rt; aux->rt = nod;
    nod=aux;
}

void balance(int *&nod)
{
    if(nod->lf->pr > nod->pr)
        rot_left(nod);
    else if(nod->rt->pr > n->pr)
        rot_right(nod);
}

void ins(Treap *&nod, int val, int pr)
{
    if(nod->val == nil)
    {
        nod->val = new Treap(val,pr,nil,nil);
        return ;
    }
    if(val < nod->val)
        ins(nod->lf, val, pr);
    else if(val > nod->val)
        ins(nod->rt, val, pr);

    balance(nod);
}

void erase(Treap *&nod, int val)
{
    if(val < nod->val)
        erase(nod->lf, val);
    else if(val > nod->val)
        erase(nod->rt, val);
    else
    {
        if(nod->rt == nil && nod->lf == nil)
            nod=nil;
        else
        {
            if(nod->lf->pr > nod->rt->pr)
                rot_left(nod);
            else rot_right(nod);
            //(nod->lf->pr > nod->rt->pr ) ? rot_left(nod) : rot_right;
            erase(nod,val);
        }
    }
}
int main()
{
    freopen("order.in","r",stdin);
    freopen("order.out","w",stdout);
    scanf("%d",&n);
    srand(unsigned(time(0)));
    R = nill = new Treap(0,0,NULL,NULL);
    for(int i = 1; i <= n; i ++ )
        ins(R, i, rand() + 1);
    return 0;
}