void update(int u) {
    h[u]=max(h[l[u]], h[r[u]])+1;
}
int diff(int u) {
    return h[l[u]]-h[r[u]];
}
void R(int &u) {
    int p=l[u];
    l[u]=r[p], r[p]=u;
    update(u), update(p);
    u=p;
}
void L(int &u) {
    int p=r[u];
    r[u]=l[p], l[p]=u;
    update(u), update(p);
    u=p;
}

void insert(int &u, int w) {
    if(!u) {
        u=++idx;
        v[u]=w;
    } else if(w<v[u]) {
        insert(l[u], w);
        if(diff(u)==2) {
            if(diff(l[u])==1) R(u);
            else L(l[u]), R(u);
        }
    } else {
        insert(r[u], w);
        if(diff(u)==-2) {
            if(diff(r[u])==-1) L(u);
            else R(r[u]), L(u);
        }
    }
    update(u);
}