struct node
{
    int val,nL,nR,hight,freq;
    node *left,*right;
    node (int v)
    {
        val=v;
        nL=nR=0;
        left=NULL;
        right=NULL;
        freq=hight=1;
    }
};
class AVLTree
{
    public:
        node* root;
        AVLTree();
        node* insert(node *r , int val);
        node* balance(node *r);
        void update(node* r);
        int bFactor (node *r);
        node* rotateRight(node *r);
        node* rotateLeft(node *r);
        int F_indx (node *r ,int val);
        int F_val (node *r,int indx);
        node* Delete (node * r ,int val);
        node* makeL (node *f , node *t);
};

AVLTree ::AVLTree ()
{
    root=NULL;
}
void AVLTree::update (node * r)
{
    int v=0;
    if(r->left) v=max(v,r->left->hight);
    if(r->right) v=max(v,r->right->hight);
    r->hight=r->freq+v;
}
node* AVLTree::insert(node *r,int val)
{
    if(r==NULL) return new node(val);
    if(val>r->val)
    {
        r->right=insert(r->right,val);
        r->nR++;
        update(r);
    }
    else if(val<r->val)
    {
        r->left=insert(r->left,val);
        r->nL++;
        update(r);
    }
    else 
    {
        r->freq++;
        r->hight++;
    }
    r=balance(r);
    return r;
}   

int AVLTree::bFactor (node *r)
{
    int diff=0;
    if(r->left) diff-=r->left->hight;
    if(r->right) diff+=r->right->hight;
    return diff;
}
node* AVLTree::rotateRight(node* r)
{
        if(r==NULL) return r;
        node* P = r->left;
        r->left = P->right;
        P->right = r;
        r->nL=((r->left) ? r->left->nL+r->left->nR+r->left->freq: 0); 
        update(r);
        P->nR=r->nL +r->nR+r->freq; 
        update(P);
        return P;
}

node* AVLTree::rotateLeft(node* r)
{
        if(r==NULL) return r;
        node* Q = r->right;
        r->right = Q->left;
        Q->left = r;
        r->nR=((r->right) ? r->right->nL+r->right->nR+r->right->freq : 0); 
        update(r);
        Q->nL=r->nL +r->nR+r->freq; 
        update(Q);
        return Q;
}

node* AVLTree::balance(node *r)
{
        int F=bFactor(r) ;
        if(F== 2)
        {
                if(bFactor(r->right) == -1)
                        r->right = rotateRight(r->right);
                r = rotateLeft(r);
        }
        else if(F== -2)
        {
                if(bFactor(r->left) == 1)
                        r->left = rotateLeft(r->left);
                r = rotateRight(r);
        }
        return r;
}

int AVLTree::F_indx(node *r ,int val)
{
    if(r==NULL) return -1;
    if(val==r->val) return r->nL+1;
    else if(val>r->val)
    {
        int res=F_indx(r->right ,val);
        return ((res==-1) ?-1 : r->nL +1+res);
    }
    else if(val <r->val)
    {
        return F_indx(r->left ,val);
    }
    
}
int AVLTree::F_val (node *r,int indx)
{
    if(r==NULL) return -1;
    if(indx >r->nL && indx <=r->nL+r->freq  ) return r->val ;
    else if( indx >r-> nL+r->freq ) return F_val(r->right,indx-r->nL-(r->freq));
    else if(indx <= r->nL) return F_val(r->left,indx);
}

node* AVLTree::makeL(node *f, node *t)
{
     if(f==NULL) return t;
     f->right=makeL(f->right,t);
     f->nR=((f->right) ? f->right->nL+f->right->nR+f->right->freq :0);
     update(f);
     f=balance(f);
     return f;
}
node* AVLTree::Delete (node *r ,int val)
{
    if(r==NULL)return r;
    if(r->val ==val)
    {
        if(--r->freq) { update(r) ;return r; }
        node *R =r->right,*L=r->left,*D=r;
        delete D ;
        if(L ==NULL)
        {
             return R;
        }
        return makeL(L,R);
    }
    if(val >r->val )
    {
        r->right=Delete(r->right ,val);
        r->nR =((r->right) ? r->right->nL+r->right->nR+r->right->freq :0);
        update(r);
    }
    else if(val < r->val)
    {
        r->left=Delete(r->left,val);
        r->nL=((r->left) ? r->left->nL+r->left->nR+r->left->freq :0);
        update(r);
    }
    r=balance(r);
    return r;
}