program pascal;
var f,g:text;
    x,t,st,dr,pos,i,n,m,mij:longint;
    v:array[1..100000] of longint;
    ok:boolean;

 procedure florin;
 begin
  st:=1;
  dr:=n;
  ok:=false;
  while (st<=dr) and (not ok) do
   begin
    mij:=st+(dr-st) div 2;
    if v[mij]=x then begin
                       ok:=true;
                       pos:=mij;
                     end
  else
   if x>v[mij] then st:=mij+1
               else dr:=mij-1;
   end;
  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,m);
 for i:=1 to m do
    begin
      readln(f,t,x);
      florin;
      if t=0 then
       begin
        if not ok then writeln(g,-1)
                  else writeln(g,pos);
        end
       else
        if t=1 then
                 begin
                  if not ok then writeln(g,dr)
                            else writeln(g,pos);
                 end
        else
         if t=2 then
                 begin
                  if not ok then writeln(g,st)
                            else writeln(g,pos);
                 end;
        end;
 close(f);
 close(g);
end.