ZZXYY's blog

type
  node=record
         ch:array[0..1]of longint;
         v,f:longint;
       end;
var
  st:array[0..100000]of longint;
  t:array[0..100000]of node;
  n,m,i,root,top,tst,c,x,y,a,b,min,sum:longint;
procedure newnode(var x:longint;f,k:longint);
begin
  if tst<>0 then
  begin
    x:=st[tst];
    dec(tst);
  end
  else begin
    inc(top);
    x:=top
  end;
  t[x].ch[0]:=0;
  t[x].ch[1]:=0;
  t[x].v:=k;
  t[x].f:=f;
end;
function cmp(x,k:longint):longint;
begin
  if t[x].ch[0]=k then exit(0) else exit(1);
end;
procedure rotate(k,c:longint);
var
  i:longint;
begin
  i:=t[k].f;
  t[i].ch[c xor 1]:=t[k].ch[c];
  t[t[k].ch[c]].f:=i;
  t[k].ch[c]:=i;
  t[k].f:=t[i].f;
  if t[i].f<>0 then t[t[i].f].ch[cmp(t[i].f,i)]:=k;
  t[i].f:=k;
end;
procedure splay(k,g:longint);
var
  x,y,f1,f2:longint;
begin
  while t[k].f<>g do
  begin
    x:=t[k].f;
    y:=t[x].f;
    if y=g then rotate(k,cmp(x,k) xor 1)
    else begin
      f1:=cmp(y,x);
      f2:=cmp(x,k);
      if f1=f2 then
      begin
        rotate(x,f1 xor 1);
        rotate(k,f1 xor 1);
      end
      else begin
        rotate(k,f1);
        rotate(k,f2);
      end;
    end;
  end;
  if g=0 then root:=k;
end;
procedure insert(k:longint);
var
  i,j,x:longint;
begin
  i:=root;
  j:=0;
  repeat
    j:=i;
    if k<t [i].v then i:=t[i].ch[0]
    else i:=t[i].ch[1];
  until i=0;
  if k<t[j].v then x:=0 else x:=1;
  newnode(t[j].ch[x],j,k);
  splay(t[j].ch[x],0);
end;
procedure find(k:longint);
var
  i:longint;
begin
  i:=root;
  repeat
    if t[i].v<=k then a:=i;
    if t[i].v>=k then b:=i;
    if t[i].v=k then exit;
    if t[i].v>k then i:=t[i].ch[0]
    else i:=t[i].ch[1];
  until i=0;
end;
procedure del(k:longint);
var
  i,j:longint;
begin
  splay(k,0);
  inc(tst);
  st[tst]:=k;
  if t[k].ch[0]=0 then
  begin
    if t[k].ch[1]=0 then
    begin
      c:=-1;
      root:=0;
      exit;
    end;
    root:=t[k].ch[1];
    t[t[k].ch[1]].f:=0;
    exit;
  end
  else begin
    i:=t[k].ch[0];
    j:=0;
    while i<>0 do
    begin
      j:=i;
      i:=t[i].ch[1];
    end;
    splay(j,root);
    root:=t[root].ch[0];
    t[root].f:=0;
    t[root].ch[1]:=t[k].ch[1];
    t[t[k].ch[1]].f:=root;
  end;
end;
begin
  read(n);
  c:=-1;
  for i:=1 to n do
  begin
    read(x,y);
    if c=-1 then
    begin
      c:=x;
      newnode(root,0,y);
    end
    else if c=x then insert(y)
    else begin
      a:=0;
      b:=0;
      min:=0;
      find(y);
      if b=0 then min:=a;
      if a=0 then min:=b;
      if (a<>0) and (b<>0) then
      if abs(t[a].v-y)< =abs(t[b].v-y) then min:=a
      else min:=b;
      sum:=(sum+abs(t[min].v-y)) mod 1000000;
      del(min);
    end;
  end;
  writeln(sum);
end.