记录编号	9608	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]统计数字	最终得分	100
用户昵称	苏轼	是否通过	通过
代码语言	Pascal	运行时间	0.705 s
提交时间	2009-04-06 20:58:09	内存使用	0.30 MiB

{
 noip2007 t1
 treap
 time:2009.4.6
}
program cch(input,output);
type
 ch=record
     data:longint;
     size:longint;
     fix:longint;
     rchild:longint;
     lchild:longint;
    end;
var
 i,n,x,tot,root:longint;
 tree:array[1..10000] of ch;

procedure left(var k:longint);
var
 y:longint;
begin
 y:=tree[k].rchild;
 tree[k].rchild:=tree[y].lchild;
 tree[y].lchild:=k;
 k:=y;
end;

procedure right(var k:longint);
var
 y:longint;
begin
 y:=tree[k].lchild;
 tree[k].lchild:=tree[y].rchild;
 tree[y].rchild:=k;
 k:=y;
end;

procedure ins(var p:longint;x:longint);
begin
 if p=0 then
  begin
   inc(tot); tree[tot].data:=x;
   tree[tot].rchild:=0; tree[tot].lchild:=0;
   tree[tot].size:=1;
   tree[tot].fix:=random(88888888);
   p:=tot;
   exit;
  end
 else
  if x=tree[p].data then inc(tree[p].size)
   else
    if x<=tree[p].data then
     begin
      ins(tree[p].lchild,x);
      if tree[tree[p].lchild].fix<tree[p].fix then right(p);
     end
    else
     begin
      ins(tree[p].rchild,x);
      if tree[tree[p].rchild].fix<tree[p].fix then left(p);
     end;
end;

procedure travel(k:longint);
begin
 if k<>0 then
  begin
   travel(tree[k].lchild);
   writeln(tree[k].data,' ',tree[k].size);
   travel(tree[k].rchild);
  end;
end;

begin
 assign(input,'pcount.in');
 assign(output,'pcount.out');
 reset(input);
 rewrite(output);
 readln(n);
 tot:=0; root:=0;
 for i:=1 to n do
  begin
   readln(x);
   ins(root,x);
  end;
 travel(root);
 close(input);
 close(output);
end.