记录编号	15438	评测结果	AAAAAAAAAA
题目名称	[USACO Mar07] 平衡的阵容	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	Pascal	运行时间	0.245 s
提交时间	2009-11-13 08:13:10	内存使用	1.54 MiB

program xmz;
var
f1,f2:text;
x,z,s:array[0..50000]of longint;
max,min:array[-50000..50000]of longint;
y:array[-50000..50000]of boolean;
n,a,ans:longint;
procedure px(l,r:longint);
var
i,j,mid,t:longint;
begin
 i:=l;j:=r;mid:=z[(i+j)div 2];
 repeat
 while z[i]<mid do inc(i);
 while z[j]>mid do dec(j);
 if i<=j then
 begin
 t:=z[i];z[i]:=z[j];z[j]:=t;
 t:=x[i];x[i]:=x[j];x[j]:=t;
 inc(i);dec(j);
 end;
 until i>j;
 if j>l then px(l,j);
 if i<r then px(i,r);
end;
begin
assign(f1,'balance.in');assign(f2,'balance.out');
reset(f1);rewrite(f2);
read(f1,n);
for a:=1 to n do
 begin
  read(f1,x[a],z[a]);
 end;
px(1,n);
for a:=1 to n do
 begin
  if x[a]=1 then s[a]:=s[a-1]+1 else s[a]:=s[a-1]-1;
  if (max[s[a]]<a)or(not y[s[a]]) then max[s[a]]:=a;
  if (min[s[a]]>a)or(not y[s[a]]) then min[s[a]]:=a;
  y[s[a]]:=true;
 end;

for a:=-50000 to 50000 do
 begin
 if a<>0 then
 begin
 if y[a] then
  if max[a]<>min[a] then
  if z[max[a]]-z[min[a]+1]>ans then ans:=z[max[a]]-z[min[a]+1];
 end
  else if z[max[a]]-z[1]>ans then ans:=z[max[a]]-z[1];
 end;
writeln(f2,ans);
close(f1);close(f2);
end.