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

function cbinara0(st,dr,x:longint):longint;
var m:longint;
begin
 while st<=dr do
  begin
   m:=(st+dr) div 2;
   if v[m]<=x then
    st:=m+1
   else
    dr:=m-1;
  end;
 m:=(st+dr) div 2;
 if v[m]>x then
  m:=m-1;
 if v[m]=x then
  cbinara0:=m
 else
  cbinara0:=-1;
end;

function cbinara1(st,dr,x:longint):longint;
var m:longint;
begin
 while st<dr do
  begin
   m:=(st+dr) div 2;
   if v[m]<=x then
    st:=m+1
   else
    dr:=m-1;
  end;
 m:=(st+dr) div 2;
 if v[m]>x then
  m:=m-1;
 cbinara1:=m;
end;

function cbinara2(st,dr,x:longint):longint;
var m:longint;
begin
 while st<dr do
  begin
   m:=(st+dr) div 2;
   if v[m]<x then
    st:=m+1
   else
    dr:=m;
  end;
 m:=(st+dr) div 2;
 if v[m]<x then
  m:=m+1;
 cbinara2:=m;
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]);
 read(f,m);
 for i:=1 to m do
  begin
   readln(f,tip,val);
   case tip of
     0:writeln(g,cbinara0(1,n,val));
     1:writeln(g,cbinara1(1,n,val));
     2:writeln(g,cbinara2(1,n,val));
   end;
  end;
 close(f);
 close(g);
end.