#include<bits/stdc++.h>
using namespace std;
 
class splay_tree{
private:
    struct node{
        node *left,*right,*parent;
        int key,sz;
        node(int key): key(key), sz(1), left(0), right(0), parent(0) {}
        node() {}
    } *root;
 
    void recalc(node *v){
        if(!v) return;
        v->sz=1;
        if(v->left) v->sz+=v->left->sz;
        if(v->right) v->sz+=v->right->sz;
    }
 
    bool is_root(node *x){
        if(!x) return false;
        if(x->parent) return true;
        return false;
    }
 
    void right_rotate(node *x){
        node *y=x->left;
        node *B=y->right;
        if(is_root(x)) root=y; else
        if(!is_root(x)){
            node *P=x->parent;
            if(P->left==x) P->left=y;
                else P->right=y;
        }
        x->left=B;
        if(B) B->parent=x;
        y->right=x;
        y->parent=x->parent;
        x->parent=y;
        recalc(y->parent);
        recalc(x);
        recalc(y);
    }
 
    void left_rotate(node *x){
        node *y=x->right;
        node *B=y->left;
        if(is_root(x)) root=y; else
        if(!is_root(x)){
            node *P=x->parent;
            if(P->left==x) P->left=y;
                else P->right=y;
        }
        x->right=B;
        if(B) B->parent=x;
        y->left=x;
        y->parent=x->parent;
        x->parent=y;
        recalc(y->parent);
        recalc(x);
        recalc(y);
    }
 
    void splay(node *x){
        if(!x) return;
        while(!is_root(x)){
            node *p=x->parent;
            if(is_root(p)){
                if(p->left==x) right_rotate(p);
                    else left_rotate(p);
            } else
            if(p->parent->left==p && p->left==x){
                right_rotate(p->parent);
                right_rotate(p);
            } else
            if(p->parent->right==p && p->right==x){
                left_rotate(p->parent);
                left_rotate(p);
            } else
            if(p->parent->left==p && p->right==x){
                left_rotate(x->parent);
                right_rotate(x->parent);
            } else {
                right_rotate(x->parent);
                left_rotate(x->parent);
            }
        }
    }
 
    node *subtree_min(node *x){
        while(x->left) x=x->left;
        return x;
    }
    node *subtree_max(node *x){
        while(x->right) x=x->right;
        return x;
    }
 
    void replace( node *p, node *v ) {
        if( !p->parent ) root = v;
        else if( p == p->parent->left ) p->parent->left = v;
        else p->parent->right = v;
        if( v ) v->parent = p->parent;
        recalc(p);
        recalc(v);
    }
 
public:
    splay_tree(): root(0) {}
 
    void insert(const int& key){
        if(!root){
            root=new node(key);
            return;
        }
        node *z=root,*p=0;
        while(z){
            p=z;
            if(z->key<key) z=z->right;
                else z=z->left;
        }
        z=new node(key);
        z->parent=p;
        if(!p) root=z; else
        if(p->key<key) p->right=z;
            else p->left=z;
        for(;p;p=p->parent) p->sz++;
        splay(z);
    }
 
    node *find(int key){
        node *z=root;
        while(z){
            if(z->key>key) z=z->left; else
            if(z->key<key) z=z->right;
                else return z;
        }
        return 0;
    }
 
    ///          TO DO
    void erase(int key){
        node *z=find(key);
        if(!z) return;
        splay(z);
        if(!z->left && !z->right){
            root=0;
            return;
        }
        if(!z->left) replace(z,z->right); else
        if(!z->right) replace(z,z->left); else {
            node *y=subtree_min(z->right);
            if(y->parent!=z){
                replace(y,y->right);
                y->right=z->right;
                y->right->parent=y;
            }
            replace(z,y);
            y->left=z->left;
            y->left->parent=y;
        }
        delete(z);
    }
 
    void write(){
        queue<node*> q;
        q.push(root);
        while(!q.empty()){
            node *v=q.front();
            q.pop();
            printf("key=%d size=%d",v->key,v->sz);
            if(v->left){
                q.push(v->left);
                printf(" left=%d",v->left->key);
            }
            if(v->right){
                q.push(v->right);
                printf(" right=%d",v->right->key);
            }
            printf("\n");
        }
    }
 
    ///   TO CHECK
    int& operator [](int k){
        node *z=root;
        int tmp=0;
        while(z){
            int q=tmp;
            if(z->left) q+=z->left->sz;
            if(q+1==k) return z->key;
            if(q>k) z=z->left; else {
                z=z->right;
                tmp++;
                if(z->left) tmp+=z->left->sz;
            }
        }
    }
 
};
 
main(){
    srand(0);
    splay_tree t;
 
    vector<int> a;
    for(int i=0;i<20;i++) a.push_back(i+1);
    random_shuffle(a.begin(),a.end());
    for(int i=0;i<10;i++) t.insert(a[i]);
    t.erase(a[0]);
 
    t.write();
 
    return 0;
}