using namespace std;
struct Node
{ int sz, label, f;
Node * p, * ch[ 2 ] ;
Node( int v= 0 ) { p = ch[ 0 ] = ch[ 1 ] = 0 ; label= v; f= 1 ; }
} ;
typedef Node* pnode;
int sz( pnode t) {
return t? t- > sz: 0 ;
}
void update( Node * x) {
if ( ! x) return ;
x- > sz= x- > f+ sz( x- > ch[ 0 ] ) + sz( x- > ch[ 1 ] ) ;
}
void rot( Node * x) {
Node * y, * z;
y = x- > p, z = y- > p;
int xp= ( x== y- > ch[ 0 ] ) ? 0 : 1 ,yp= ( z) ? ( ( y== z- > ch[ 0 ] ) ? 0 : 1 ) : - 1 ;
if ( ( y- > ch[ xp] = x- > ch[ 1 ^ xp] ) ) y- > ch[ xp] - > p= y;
x- > ch[ 1 ^ xp] = y, y- > p = x;
if ( ( x- > p= z) ) z- > ch[ yp] = x;
update( y) ;
}
void splay( Node * x) {
if ( ! x) return ;
while ( x- > p) rot( x) ;
update( x) ;
}
void join ( pnode & c,Node * L , Node * R) {
if ( ! L||! R) { c= ( ! L) ? R: L,update( c) ; return ; }
c= L;
while ( c- > ch[ 1 ] ) c= c- > ch[ 1 ] ;
splay( c) ; c- > ch[ 1 ] = R; if ( R) R- > p= c;
update( c) ;
}
Node * find ( Node * T ,int k,Node * p= 0 ) {
if ( ! T) return p;
return ( T- > label== k) ? T: ( T- > label> k) ? find( T- > ch[ 0 ] ,k,T) : find( T- > ch[ 1 ] ,k,T) ;
}
void split ( pnode T,pnode & L,pnode & R ,int x) {
if ( ! T) { L= R= NULL ; return ; }
T= find( T,x) ; splay( T) ;
if ( T- > label> x) L= T- > ch[ 0 ] ,T- > ch[ 0 ] = 0 ,R= T;
else R= T- > ch[ 1 ] ,T- > ch[ 1 ] = 0 ,L= T;
if ( L) L- > p= 0 ; if ( R) R- > p= 0 ;
update( L) ; update( R) ;
}
void insert( pnode & T,int x) {
pnode n= new Node( x) ;
pnode l= 0 ,r= 0 ;
if ( T) {
T= find( T,x) ; splay( T) ;
if ( T- > label== x) T- > f++ ;
else {
split( T, l, r, x) ,n- > ch[ 0 ] = l,n- > ch[ 1 ] = r;
if ( l) l- > p = n;
if ( r) r- > p = n;
T= n;
}
}
if ( ! T) T= n;
update( T) ;
}
void erase ( pnode & n,int k) {
if ( ! n) return ;
n= find( n,k) ; splay( n) ;
if ( n- > label== k) {
n- > f-- ;
if ( ! n- > f) {
if ( n- > ch[ 0 ] ) n- > ch[ 0 ] - > p= 0 ;
if ( n- > ch[ 1 ] ) n- > ch[ 1 ] - > p= 0 ;
join( n,n- > ch[ 1 ] ,n- > ch[ 0 ] ) ;
}
}
}
CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CnN0cnVjdCBOb2RlCnsgICBpbnQgc3osIGxhYmVsLCBmOwogICAgTm9kZSAqcCwgKmNoWzJdOwogICAgTm9kZShpbnQgdj0wKSB7IHAgPSBjaFswXSA9IGNoWzFdID0gMDtsYWJlbD12O2Y9MTsgfQp9Owp0eXBlZGVmIE5vZGUqIHBub2RlOwppbnQgc3oocG5vZGUgdCl7CiAgICByZXR1cm4gdD90LT5zejowOwp9CnZvaWQgdXBkYXRlKE5vZGUgKngpewogICAgaWYgKCF4KXJldHVybiA7CiAgICB4LT5zej14LT5mK3N6KHgtPmNoWzBdKStzeih4LT5jaFsxXSk7Cn0Kdm9pZCByb3QoTm9kZSAqeCl7CiAgICBOb2RlICp5LCAqejsKICAgIHkgPSB4LT5wLCB6ID0geS0+cDsKICAgIGludCB4cD0oeD09eS0+Y2hbMF0pPzA6MSx5cD0oeik/KCh5PT16LT5jaFswXSk/MDoxKTotMTsKICAgIGlmICgoeS0+Y2hbeHBdPXgtPmNoWzFeeHBdKSl5LT5jaFt4cF0tPnA9eTsKICAgIHgtPmNoWzFeeHBdID0geSwgeS0+cCA9IHg7CiAgICBpZiAoKHgtPnA9eikpei0+Y2hbeXBdPXg7CiAgICB1cGRhdGUoeSk7Cn0KCnZvaWQgc3BsYXkoTm9kZSAqeCl7CiAgICBpZiAoIXgpcmV0dXJuIDsKICAgIHdoaWxlICh4LT5wKXJvdCh4KTsKICAgIHVwZGF0ZSh4KTsKfQp2b2lkICBqb2luIChwbm9kZSAmIGMsTm9kZSAqTCAsIE5vZGUgKlIpewogICAgaWYgKCFMfHwhUil7IGM9KCFMKT9SOkwsdXBkYXRlKGMpO3JldHVybiA7fQogICAgYz1MOwogICAgd2hpbGUgKGMtPmNoWzFdKWM9Yy0+Y2hbMV07CiAgICBzcGxheShjKTtjLT5jaFsxXT1SO2lmIChSKSBSLT5wPWM7CiAgICB1cGRhdGUoYyk7Cn0KTm9kZSAqIGZpbmQgKE5vZGUgKiBUICxpbnQgayxOb2RlICpwPTApewogICAgaWYgKCFUKXJldHVybiBwOwogICAgcmV0dXJuIChULT5sYWJlbD09ayk/VDooVC0+bGFiZWw+ayk/ZmluZChULT5jaFswXSxrLFQpOmZpbmQoVC0+Y2hbMV0sayxUKTsKfQp2b2lkIHNwbGl0IChwbm9kZSBULHBub2RlICYgTCxwbm9kZSAmIFIgLGludCB4KXsKICAgIGlmICghVCl7IEw9Uj1OVUxMO3JldHVybiA7fQogICAgVD1maW5kKFQseCk7c3BsYXkoVCk7CiAgICBpZiAoVC0+bGFiZWw+eClMPVQtPmNoWzBdLFQtPmNoWzBdPTAsUj1UOwogICAgZWxzZSBSPVQtPmNoWzFdLFQtPmNoWzFdPTAsTD1UOwogICAgaWYgKEwpTC0+cD0wO2lmIChSKVItPnA9MDsKICAgIHVwZGF0ZShMKTt1cGRhdGUoUik7Cn0KCnZvaWQgaW5zZXJ0KHBub2RlICYgVCxpbnQgeCl7CiAgICBwbm9kZSBuPW5ldyBOb2RlKHgpOwogICAgcG5vZGUgbD0wLHI9MDsKICAgIGlmIChUKSB7CiAgICAgICAgVD1maW5kKFQseCk7c3BsYXkoVCk7CiAgICAgICAgaWYgKFQtPmxhYmVsPT14KVQtPmYrKzsKICAgICAgICBlbHNlewogICAgICAgIHNwbGl0KFQsIGwsIHIsIHgpLG4tPmNoWzBdID0gbCxuLT5jaFsxXSA9IHI7CiAgICAgICAgICAgIGlmIChsKWwtPnAgPSBuOwogICAgICAgICAgICBpZiAocilyLT5wID0gbjsKICAgICAgICAgICAgVD1uOwogICAgICAgIH0KICAgIH0KICAgIGlmICghVClUPW47CiAgICB1cGRhdGUoVCk7Cn0Kdm9pZCBlcmFzZSAocG5vZGUgJiBuLGludCBrKXsKICAgIGlmICghbilyZXR1cm4gOwogICAgbj1maW5kKG4sayk7c3BsYXkobik7CiAgICBpZiAobi0+bGFiZWw9PWspewogICAgICAgIG4tPmYtLTsKICAgICAgICBpZiAoIW4tPmYpewogICAgICAgICAgICBpZiAobi0+Y2hbMF0pbi0+Y2hbMF0tPnA9MDsKICAgICAgICAgICAgaWYgKG4tPmNoWzFdKW4tPmNoWzFdLT5wPTA7CiAgICAgICAgICAgIGpvaW4obixuLT5jaFsxXSxuLT5jaFswXSk7CiAgICAgICAgfQogICAgfQp9