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

procedure caut_bin1 ;
var st,dr,mijloc:longint;
begin
  st:=1; dr:=n;
  while st<=dr do
  begin
   mijloc:=(st+dr) div 2;
   if v[mijloc]=val then
    if mijloc>poz then
     poz:=mijloc;
   if v[mijloc]>val then
    dr:=mijloc-1
   else
    st:=mijloc+1;
  end;
end;

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

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

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