#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<ctime>

using namespace std;

struct Treenode

{

    int size;

    int fix;

    int weight;

    int key;

    Treenode *left;

    Treenode *right;

};

class Treaptree

{

    private:

        Treenode *null;

    public:

        Treenode *root;

        Treaptree()

        {

            null=new Treenode;

            null->key=;

            null->weight=;

            null->size=;

            null->left=null;

            null->right=null;

            null->fix=;

            root=null;

        } 

    void Treap_left(Treenode *now)

    {

        Treenode *tmp=now->right;

        now->right=tmp->left;

        tmp->left=now;

        tmp->size=now->size;

        now->size=now->left->size+now->right->size+now->weight;

        now=tmp;

    }

    void Treap_right(Treenode *now)

    {

        Treenode *tmp=now->left;

        now->left=tmp->right;

        tmp->right=now;

        tmp->size=now->size;

        now->size=now->left->size+now->right->size+now->weight;

        now=tmp;

    }

    void insert(Treenode *&now,int key)

    {

        if(now==null)

        {

            now=new Treenode;

            now->key=key;

            now->size=;

            now->weight=;

            now->fix=rand();

            now->left=null;

            now->right=null;

        }

        else if(key==now->key)

        {

            now->weight++;

        }

        else if(key<now->key)

        {

            insert(now->left,key);

            if(now->left->fix<now->fix) Treap_right(now);

        }

        else if(key>now->key)

        {

            insert(now->right,key);

            if(now->left->fix<now->fix) Treap_left(now);

        }

        now->size=now->left->size+now->right->size+now->weight;

    }

    bool find(Treenode *now,int key)

    {

        if(now==null)return false;

        if(key<now->key)return find(now->left,key);

        else if(key>now->key)return find(now->right,key);

        else return true;

    }

    void Delete(Treenode *&now,int key)

    {

        if(now==null)return;

        if(key<now->key)Delete(now->left,key);

        else if(key>now->key)Delete(now->right,key);

        else

        {

            if(now->weight>)now->weight--;

            else

            {

                if(now->left==null&&now->right==null)

                {

                    delete now;

                    now=null;

                }

                else

                {

                    if(now->left->fix<now->right->fix)Treap_left(now);

                    else Treap_right(now);

                    Delete(now,key);

                }

                now->size=now->left->size+now->right->size+now->weight;

            }

        }

    }

};

int main()

{

    return ;

}