int isroot(int x) {return ch[fa[x]][0]!=x&&ch[fa[x]][1]!=x;}
int idt(int x) {return ch[fa[x]][1]==x;}
void swp(int x) {
    if(!x) return ;
    rev[x]^=1;
    swap(ls,rs);
}
void pushdown(int x) {
    if(rev[x]) {
        rev[x]=0;
        swp(ls);
        swp(rs);
    }
}
void pushup(int x) {
    if(!x) return;
    if(x<=n) ma[x]=-INF;
    else ma[x]=val[x];
    if(ls) cmax(ma[x],ma[ls]);
    if(rs) cmax(ma[x],ma[rs]);
}
void pushall(int x) {
    if(!isroot(x)) pushall(fa[x]);
    pushdown(x);
}
void add(int y,int x,int i) {ch[fa[x]=y][i]=x;}
void rotate(int x) {
    int y=fa[x],i=idt(x);
    if(isroot(y)) fa[x]=fa[y];
    else add(fa[y],x,idt(y));
    add(y,ch[x][!i],i);
    add(x,y,!i);
    pushup(y);
}
void splay(int x) {
    pushall(x);
    for(int y;y=fa[x],!isroot(x);rotate(x)) {
        if(!isroot(y)) rotate(idt(x)==idt(y)?y:x);
    }
    pushup(x);
}
void access(int x) {
    for(int p=0;x;p=x,x=fa[x]) {
        splay(x);
        ch[x][1]=p;
        pushup(x);
    }
}
void makeroot(int x) {
    access(x);
    splay(x);
    swp(x);
}
void split(int u,int v) {
    makeroot(u);
    access(v);
    splay(u);
}
void cut(int u,int v) {
    split(u,v);
    ch[u][1]=fa[v]=0;
    pushup(u);
}
int findroot(int x) {
	access(x);
	splay(x);
	while(pushdown(x), ls) x = ls;
	splay(x);
}