program lt;
var n,m,num,p,i,k,code,head:longint;
key,left,right,s:array[1..100000] of longint;
ss:string;

procedure left_rotate(var x:longint);
var y:longint;
begin
y:=right;
right:=left;
left:=x;
s:=s;
s:=s]+s]+1;
x:=y;
end;
procedure right_rotate(var x:longint);
var y:longint;
begin
y:=left;
left:=right;
right:=x;
s:=s;
s:=s]+s]+1;
x:=y;
end;
procedure maintain(var t:longint;flag:boolean);
begin
if flag then
if s]]>s] then
left_rotate(t)
else
if s]]>s] then
begin
right_rotate(right);
left_rotate(t);
end
else exit
else
if s]]>s] then
right_rotate(t)
else
if s]]>s] then
begin
left_rotate(left);
right_rotate(t);
end
else exit;
maintain(left,false);
maintain(right,true);
maintain(t,false);
maintain(t,true);
end;
procedure insert(k:longint;var t:longint);
begin
if t=0 then
begin
inc(num);
t:=num;
s:=1;
left:=0;right:=0;
key:=k;
end
else
begin
inc(s);
if k=key);
end;
end;
function delete(k:longint;var t:longint):longint;
begin
dec(s);
if (k=key)or(kkey)and(right=0) then
begin
delete:=key;
if (left=0) or (right=0) then t:=left+right
else key:=delete(k+1,left);
end
else
if k