记录编号	108264	评测结果	AAAAAAAAAA
题目名称	[HDU 1512] 爱争吵的猴子	最终得分	100
用户昵称	zgyzhaoguangyang	是否通过	通过
代码语言	Pascal	运行时间	1.035 s
提交时间	2014-07-03 10:51:25	内存使用	6.08 MiB

type segment_tree=record
  l,r,dat:longint;
end;
var
  dat,f,a,b,ver,l,r,p,q:array[0..100005] of longint;
  t:array[0..350005] of segment_tree;
  n,m:longint;

procedure init;
var i:longint;
begin
   readln(n);
   for i:=1 to n do read(dat[i]);
   for i:=1 to n do begin
                    r[i]:=i;
                    f[i]:=i;
                    end;
   read(m);
  for i:=1 to m  do
   read(a[i],b[i]);
end;

function find(x:longint):longint;
begin
  if f[x]=x then exit(x);
  f[x]:=find(f[x]);
  exit(f[x]);
end;

procedure merge(x,y:longint);
begin
   f[y]:=x;
   ver[r[x]]:=y;
   r[x]:=r[y];
end;

procedure buildtree(p,l,r:longint);
var mid:longint;
begin
   t[p].l:=l;t[p].r:=r;
   if l=r then
   begin
       t[p].dat:=q[l];
       exit;
   end;
   mid:=(l+r)>>1;
   buildtree(p<<1,l,mid);
   buildtree(p<<1+1,mid+1,r);
   if dat[t[p<<1].dat]>dat[t[p<<1+1].dat] then
     t[p].dat:=t[p<<1].dat else
     t[p].dat:=t[p<<1+1].dat;
end;


procedure build;
var i,j,fx,fy,tot:longint;
begin
   for i:=1 to m do
   begin
          fx:=find(a[i]);
          fy:=find(b[i]);
          if fx<>fy then merge(fx,fy);
   end;
   tot:=0;
  for i:=1 to n do
   if (find(i)=i) then
  begin
       j:=i;
       while j<>0 do
       begin
            inc(tot);
            q[tot]:=j;
            p[j]:=tot;
            j:=ver[j];
       end;
  end;
  buildtree(1,1,n);
end;

procedure change(p,l,r:longint);
var mid:longint;
begin
   if (t[p].l=t[p].r) then
    begin
         dat[q[l]]:=dat[q[l]]>>1;
         t[p].dat:=q[l];
         exit;
    end;
  mid:=(t[p].l+t[p].r)>>1;
  if (mid>=l) then change(p<<1,l,r)
              else change(p<<1+1,l,r);
  if dat[t[p<<1].dat]>dat[t[p<<1+1].dat] then
     t[p].dat:=t[p<<1].dat else
     t[p].dat:=t[p<<1+1].dat;
end;

function ask(p,l,r:longint):longint;
var mid,temp,tem:longint;
begin
   if (t[p].l>=l) and (t[p].r<=r) then
     exit(t[p].dat);
   temp:=0;mid:=(t[p].l+t[p].r)>>1;tem:=0;
   if(mid>=l) then temp:=ask(p<<1,l,r);
   if (mid<r) then tem:=ask(p<<1+1,l,r);
   if (tem=0) then exit(temp);
   if (temp=0) then exit(tem);
   if (dat[temp]>dat[tem]) then exit(temp)
                           else exit(tem);
end;

procedure work;
var i,fx,fy,x1,y1:longint;
begin
   for i:=1 to n do begin
                        f[i]:=i;l[i]:=p[i];r[i]:=p[i];
                    end;
   for i:=1 to m do
   begin
        fx:=find(a[i]);
        fy:=find(b[i]);
        if fx=fy then begin
                       writeln(-1);
                       continue;
                      end;
        x1:=ask(1,l[fx],r[fx]);
        y1:=ask(1,l[fy],r[fy]);
        change(1,p[x1],p[x1]);
        change(1,p[y1],p[y1]);
        f[fy]:=fx;
        r[fx]:=r[fy];
        writeln(dat[ask(1,l[fx],r[fx])]);
   end;
end;

begin
assign(input,'monkeyk.in');reset(input);
assign(output,'monkeyk.out');rewrite(output);
   init;
   build;
   work;
close(input);close(output);
end.