program cautare_binara;
var f,g:text;
    n,m,i:longint;
    v:array of longint;
    bufin,bufout:array[1..65000] of byte;
    tip:byte;
    valoare,poz:longint;

procedure caut_bin1(st,dr,valoare:longint; var poz:longint);
var mijloc:longint;
begin
 if st=dr then
 begin
  if v[st]=valoare then
   if st>poz then
    poz:=st;
 end
 else
 begin
  mijloc:=(st+dr) div 2;
  caut_bin1 (st,mijloc,valoare,poz);
  caut_bin1(mijloc+1,dr,valoare,poz);
 end;
end;

procedure caut_bin2(st,dr,valoare:longint; var poz:longint);
var mijloc:longint;
begin
 if st=dr then
 begin
  if v[st]<=valoare then
   if st>poz then
    poz:=st;
 end
 else
 begin
  mijloc:=(st+dr) div 2;
  caut_bin2 (st,mijloc,valoare,poz);
  caut_bin2(mijloc+1,dr,valoare,poz);
 end;
end;

procedure caut_bin3 (st,dr,valoare:longint; var poz:longint);
var mijloc:longint;
begin
 if st=dr then
 begin
  if v[st]>=valoare then
   if st<poz then
    poz:=st;
 end
 else
 begin
  mijloc:=(st+dr) div 2;
  caut_bin3 (st,mijloc,valoare,poz);
  caut_bin3 (mijloc+1,dr,valoare,poz);
 end;
end;

begin
 assign (f,'cautbin.in'); reset (f);
 assign (g,'cautbin.out'); rewrite (G);
 settextbuf (f,bufin); settextbuf (g,bufout);
 readln (f,n);
 setlength (V,n+1);
 for i:=1 to n do
  read (f,v[i]);
 readln (f);
 readln (F,m);
 for i:=1 to m do
 begin
  readln (f,tip,valoare);
  if tip=0 then
  begin
   poz:=-1;
   caut_bin1(1,n,valoare,poz);
   writeln (G,poz);
  end
  else
   if tip=1 then
   begin
    poz:=0;
    caut_bin2(1,n,valoare,poz);
    writeln (G,poz);
   end
   else
   begin
    poz:=n+1;
    caut_bin3(1,n,valoare,poz);
    writeln (G,poz);
   end;
 end;
 close (f); close (g);
end.