记录编号	23240	评测结果	AAAAAAAAAA
题目名称	[HNOI 2004] 宠物收养所	最终得分	100
用户昵称	donny	是否通过	通过
代码语言	Pascal	运行时间	0.417 s
提交时间	2011-03-04 14:00:32	内存使用	1.94 MiB

program pet;
var
  t,head:longint;
  a,p,left,right,typ,ran:array[1..80000]of longint;
  n,i,s,r,max,m:longint;

procedure turnleft(const x:longint);
var
  o,q,s:longint;
begin
  o:=p[x];
  q:=left[right[x]];
  s:=right[x];
  if left[o]=x then left[o]:=s
  else right[o]:=s;
  p[s]:=o;
  if head=x then head:=s;
  left[s]:=x;
  p[x]:=s;
  right[x]:=q;
  p[q]:=x;
end;

procedure turnright(const x:longint);
var
  o,q,s:longint;
begin
  o:=p[x];
  q:=left[x];
  s:=right[q];
  if left[o]=x then left[o]:=q
  else right[o]:=q;
  if head=x then head:=q;
  p[q]:=o;
  right[q]:=x;
  p[x]:=q;
  p[s]:=x;
  left[x]:=s;
end;  

function pre(const x:longint):longint;
var
  o,q:longint;
begin
  if left[x]<>0 then
  begin
    o:=left[x];
    q:=right[o];
    while q<>0 do
    begin
      o:=q;
      q:=right[o];
    end;
    exit(o);
  end
  else
  begin
    o:=p[x];
    q:=x;
    while (o<>0)and(left[o]=q) do
    begin
      q:=o;
      o:=p[q];
    end;
    exit(o);
  end;
end;

function suc(const x:longint):longint;
var
  o,q:longint;
begin
  if right[x]<>0 then
  begin
    o:=right[x];
    q:=left[o];
    while q<>0 do
    begin
      o:=q;
      q:=left[o];
    end;
    exit(o);
  end
  else
  begin
    o:=p[x];
    q:=x;
    while (o<>0)and(right[o]=q) do
    begin
      q:=o;
      o:=p[q];
    end;
    exit(o);
  end;
end;

procedure balanceup(const x:longint);
begin
  while (ran[x]<ran[p[x]])and(p[x]<>0) do
  begin
    if left[p[x]]=x then turnright(p[x])
    else turnleft(p[x]);
  end;
end;

procedure insert(const x,y:longint);
var
  o,q:longint;
begin
  inc(m);
  a[m]:=y;
  typ[m]:=x;
  ran[m]:=random(1000000);
  o:=head;
  if a[m]>a[o] then q:=right[o]
  else q:=left[o];
  while q<>0 do
  begin
    o:=q;
    if a[m]>a[o] then q:=right[o]
    else q:=left[o];
  end;
  p[m]:=o;
  if a[m]>a[o] then right[o]:=m
  else left[o]:=m;
  balanceup(m);
end;

procedure delete(const x:longint);
var
  o,q:longint;
begin
  if (left[x]=0)or(right[x]=0) then
  begin
    if (left[x]=0)and(right[x]=0) then
    begin
      if head=x then
      begin
        t:=2;
        head:=0;
      end
      else
      begin
        o:=p[x];
        if left[o]=x then left[o]:=0
        else right[o]:=0;
      end;
    end
    else
    begin
      if left[x]<>0 then q:=left[x]
      else q:=right[x];
      if x=left[p[x]] then left[p[x]]:=q
      else right[p[x]]:=q;
      p[q]:=p[x];
      if head=x then head:=q;
    end;
  end
  else
  begin
    o:=ran[x] mod 2;
    if o=1 then q:=pre(x)
    else q:=suc(x);
    a[x]:=a[q];
    delete(q);
  end;
end;

procedure search(const x,y:longint);
var
  o,q,s,t:longint;
begin
  o:=head;
  if y>a[o] then q:=right[o]
  else q:=left[o];
  while q<>0 do
  begin
    o:=q;
    if y>a[o] then q:=right[o]
    else q:=left[o];
  end;
  
  if (left[o]=0)and(right[o]=0)and(head=o) then
  begin
    max:=(max+abs(a[o]-y))mod 1000000;
    delete(o);
    exit;
  end;
  
  if y>a[o] then 
  begin
    s:=suc(o);
    if s=0 then 
    begin
      s:=pre(o);
      t:=o;
      o:=s;
      s:=t;
    end; 
  end  
  else
  begin
    s:=pre(o);
    if s=0 then s:=suc(o)
    else
    begin
      t:=o;
      o:=s;
      s:=t;
    end;
  end;
  t:=abs(y-a[o]);
  if abs(a[s]-y)<t then
  begin
    max:=(max+abs(a[s]-y)) mod 1000000;
    delete(s);
  end
  else
  begin
    max:=(max+t) mod 1000000;
    delete(o);
  end;
  
end;  
  
procedure main(const x,y:longint);
begin
  if t=2 then
  begin
    t:=x;
    inc(m);
    a[m]:=y;
    p[m]:=0;
    typ[m]:=x;
    ran[m]:=random(1000000);
    head:=m;
  end
  else
  begin
    if t=x then
      insert(x,y)
    else
    begin
      search(x,y);
    end;
  end;
end;

begin
  assign(input,'pet.in');
  reset(input);
  assign(output,'pet.out');
  rewrite(output);
  
  readln(n);
  
  t:=2;
  head:=0;
  randomize;
  m:=0;
  max:=0;
  
  for i:=1 to n do
  begin
    readln(s,r);
    main(s,r);
  end;
  
  writeln(max);
  close(input);
  close(output);
end.