#include <bits/stdc++.h>

using namespace std;

class Treap
{
public:

    int key;
    int prior;
    int sz;
    int val;

    bool rev;

    Treap *L;
    Treap *R;

    Treap(int _key,int _val)
    {
        key=_key;
        prior=rand()%1000000;
        sz=1;
        val=_val;

        rev=0;

        L=R=NULL;
    }
};

int sz(Treap *T)
{
    if(T==NULL)
        return 0;
    return T->sz;
}

void UpdateSz(Treap *T)
{
    T->sz=1+sz(T->L)+sz(T->R);
}

void UpdateKey(Treap *T,int add)
{
    T->key=add+1+sz(T->L);
}

void Merge(Treap *T,Treap *a,Treap *b,int add)
{
    Treap *aux=T;

    if(a==NULL || b==NULL)
    {
        T=(a!=NULL?a:b);
    }
    else
    {
        int v1=a->prior;
        int v2=b->prior;

        if(v1>v2)
        {
            Merge(a->R,a->R,b);
            T=a;
        }
        else
        {
            Merge(b->L,a,b->L);
            T=b;
        }
    }

    delete aux;
}

void Split(Treap *T,int x,Treap *l,Treap *r,int add)
{
    if(T==NULL)
    {
        l=r=NULL;
    }
    else
    {
        Treap *aux=T;

        int v=T->key;

        if(x<v)
        {
            Split(T->L,x,l,r);
            Merge(r,r,T->R);
        }
        else
        {
            Split(T->R,x,l,r);
            Merge(l,T->L,l);
        }

        delete aux;
    }
}

void Insert(Treap *T,Treap *t,int add)
{
    if(T==NULL)
    {
        T=t;
    }
    else
    {
        if(T->prior<t->prior)
        {
            Split(T,t->key,t->L,t->R);
            T=t;
        }
        else
        {
            if(T->key>t->key)
                Insert(T->L,t);
            else
                Insert(T->R,t);
        }
    }
}

int F(Treap *T,int x,int add)
{
    if(T!=NULL)
    {
        if(T->key==x)
            return T->val;
        if(x<T->key)
            return F(T->L,x);
        return F(T->R,x);
    }
    return -1;
}

void Erase(Treap *T,int i,int j)
{
    Treap *T1,*T2,*T3;

    Split(T,i,T1,T2);
    Split(T2,j-i+2,T2,T3);

    delete T2;

    Merge(T,T1,T3);
}

int main()
{

    return 0;
}