很水的平衡树，看到C++们直接STL，我很是郁闷！还好，虽然咱pas党代码长，但我一次Ac还是很开心地～
program h8oj1208;
type link=^node; node=record value,size:longint; pre:link; ch:array[0..1] of link; end;
var root:link;
now,n,a,b,ans:longint;
pl,pr:link;
procedure updata(x:link);
begin x^.size:=1;
if x^.ch[0]<>nil then inc(x^.size,x^.ch[0]^.size);
if x^.ch[1]<>nil then inc(x^.size,x^.ch[1]^.size);
end;
procedure rotate(x:link;k:longint);
var f:link;
begin f:=x^.pre;
f^.ch[1-k]:=x^.ch[k];if x^.ch[k]<>nil then x^.ch[k]^.pre:=f;
x^.pre:=f^.pre; if f^.pre<>nil then if f^.pre^.ch[0]=f then f^.pre^.ch[0]:=x else f^.pre^.ch[1]:=x;
x^.ch[k]:=f; f^.pre:=x; if f=root then root:=x;
updata(f); updata(x);
end;
procedure splay(x,goal:link);
var y,z:link;
begin
while x^.pre<>goal do
if x^.pre^.pre=goal then
if x^.pre^.ch[0]=x then rotate(x,1) else rotate(x,0)
else begin
y:=x^.pre; z:=y^.pre;
if z^.ch[0]=y then
if y^.ch[0]=x then begin rotate(y,1); rotate(x,1); end
else begin rotate(x,0); rotate(x,1); end
else if y^.ch[1]=x then begin rotate(y,0); rotate(x,0); end
else begin rotate(x,1); rotate(x,0); end;
end;
end;
procedure insert(x:longint);
var p:link;
procedure find(var r:link);
begin
if r=nil then begin
new(r); with r^ do begin
size:=1; value:=x;
ch[0]:=nil; ch[1]:=nil;
end;
p:=r;
end else begin
inc(r^.size);
if x>r^.value then begin find(r^.ch[1]); r^.ch[1]^.pre:=r; end
else begin find(r^.ch[0]); r^.ch[0]^.pre:=r; end;
end;
end;
begin find(root); root^.pre:=nil; splay(p,nil);
end;
function pre(x:longint):link;
procedure find(r:link);
begin
if r=nil then exit;
if r^.value<=x then begin
pre:=r; find(r^.ch[1]);
end else find(r^.ch[0]);
end;
begin pre:=nil;find(root);Splay(pre,nil);
end;
function succ(x:longint):link;
procedure find(r:link);
begin
if r=nil then exit;
if r^.value>=x then begin
succ:=r; find(r^.ch[0]);
end else find(r^.ch[1]);
end;
begin succ:=nil; find(root); splay(succ,nil);
end;
procedure delete(r:link);
var p:link;
begin
splay(r,nil);
if root^.ch[0]=nil then begin
root:=root^.ch[1];
root^.pre:=nil;
end else begin
p:=root^.ch[0];
while p^.ch[1]<>nil do p:=p^.ch[1];
splay(p,root);
p^.pre:=nil;
p^.ch[1]:=root^.ch[1];
root^.ch[1]^.pre:=p;
root:=p;
updata(root);
end;
end;
begin
assign(input,'h8oj1208.in'); reset(input);
assign(output,'h8oj1208.out'); rewrite(output);
ans:=0;
root:=nil;insert(-(1 shl 29));insert(1 shl 29);
readln(n); while n>0 do begin dec(n);
readln(a,b);
if (root^.size=2)or(a=now) then begin
insert(b); now:=a;
end else begin
pl:=pre(b); pr:=succ(b);
writeln(pl^.value,'<=',b,'<=',pr^.value);
if pr^.value-b<b-pl^.value then begin
inc(ans,pr^.value-b);
delete(pr)
end else begin
inc(ans,b-pl^.value);
delete(pl);
end;
ans:=ans mod 1000000;
end;
end;
write(ans);
close(input); close(output);
end.
