program pascal;
var f,g:text;  st,dr,n,i,m,min,max,mij,x,pos,t: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
    if (x>v[st]) and (x<v[dr]) then
                     begin
                      min:=st;
                      max:=dr;
                     end;
    mij:=(st+dr) 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;
   if min=0 then min:=n;
   if max=0 then max:=1;
 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,min)
                            else writeln(g,pos);
                 end
               else
        if t=2 then
                begin
                 if not ok then writeln(g,max)
                           else writeln(g,pos);

                 end;
       end;
 close(f);
 close(g);
end.