program pascal;
var f,g:text;
    mij,st,dr,i,j,t,x,n,m:longint;
    v:array[1..100001] of longint;
    ok:boolean;
 procedure flo1;
 begin
  ok:=false;
  while (st<=dr) and (not ok) do
   begin
    mij:=(st+dr) div 2;
    if x=v[mij] then
         begin
          ok:=true;
          writeln(g,mij);
         end
       else
      if x>v[mij] then st:=mij+1
                  else dr:=mij-1;
    end;
   if not ok then writeln(g,-1);
 end;

 procedure flo2;
  begin
  st:=1;
  dr:=n;
  ok:=false;
  while (st<dr) and (not ok) do
   begin
    mij:=(st+dr) div 2;
      if x>v[mij] then st:=mij+1
                  else dr:=mij;
    end;
    mij:=(st+dr) div 2;
   if v[mij]>x then  dec(mij);
   writeln(g,mij);
  end;

  procedure flo3;
  begin
  st:=1;
  dr:=n;
   while st<dr do
    begin
     mij:=(st+dr) div 2;
     if v[mij]<x then st:=mij+1
                 else dr:=mij;
    end;
    mij:=(st+dr) div 2;
    if v[mij]<x then inc(mij);
    writeln(g,mij);
 end;

begin
assign(f,'cautbin.in'); reset(f);
assign(g,'cautbin.out'); rewrite(g);
readln(f,n);
for i:=1 to n do read(f,v[i]);
readln(f);
readln(f,m);
for j:=1 to m do
 begin
  readln(f,t,x);
  st:=1;
  dr:=n;
  if t=0 then flo1
         else
  if t=1 then flo2
         else
  if t=2 then flo3
 end;
close(f);
close(g);
end.