var a:array[1..100003]of longint;
    n,m,i,x,rez:longint;
    tip:byte;
    f,fo:text;
procedure cbin0(st,dr,x:longint;var rez:longint);
var m:longint;
begin
if st<dr then
 begin
  m:=st+(dr-st)div 2;
  if x>a[m] then
   begin
    cbin0(st,m,x,rez)
   end
              else
   begin
    if a[m]=x then rez:=m;
    cbin0(m+1,dr,x,rez)
   end
 end
          else
 if a[st]=x then rez:=st;
end;


procedure cbin1(st,dr,x:longint;var rez:longint);
var m:longint;
begin
if st<dr then
 begin
  m:=st+(dr-st)div 2;
  if x>=a[m] then
   begin
    rez:=m;
    cbin1(m+1,dr,x,rez)
   end
              else
   begin
    cbin1(st,m,x,rez)
   end
 end
          else
 if a[st]<=x then rez:=st;
end;

procedure cbin2(st,dr,x:longint;var rez:longint);
var m:longint;
begin
if st<dr then
 begin
  m:=st+(dr-st)div 2;
  if x>a[m] then
   begin
    cbin2(m+1,dr,x,rez)
   end
              else
   begin
    rez:=m;
    cbin2(st,m,x,rez)
   end
 end
          else
 if a[st]>=x then rez:=st;
end;

begin
assign(f,'cautbin.in');
assign(fo,'cautbin.out');
reset(f);
readln(f,n);
for i:=1 to n do
 read(f,a[i]);
readln(f);
readln(f,m);
rewrite(fo);
for i:=1 to m do
 begin
  readln(f,tip,x);
  rez:=-1;
  case tip of
   0:cbin0(1,n,x,rez);
   1:cbin1(1,n,x,rez);
   2:cbin2(1,n,x,rez);
  end;
 writeln(fo,rez);
 end;
close(fo);
close(f);
end.