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

  procedure dreapta;
  begin
   st:=(st+dr) div 2;
  end;

  procedure stanga;
  begin
   dr:=(st+dr) div 2;
  end;

  procedure florin;
  begin
                      st:=1;
                      dr:=n;
                      ok:=false;
                      bun:=true;
                      repeat
                          if (not ok) and (st+1=dr) then bun:=false;
                          q:=(st+dr);
                          if p>v[q div 2] then dreapta
                                          else
                          if p<v[q div 2] then stanga
                                          else
                          if p=v[q div 2] then begin
                                                 ok:=true;
                                               end;
                       until ok or (not bun);
  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);
read(f,m);

 for i:=1 to m do
   begin
     readln(f,t,p);
     if t=0 then
              begin
               florin;
               if ok then writeln(g,q div 2)
                     else writeln(g,-1);
              end;
     if t=1 then begin
                    florin;
                    if (not bun) and (dr=n) then writeln(g,q div 2+1)
                                       else
                                           writeln(g,q div 2)
                  end;
     if t=2 then begin
                    florin;
                    if not bun then writeln(g,q div 2+1)
                               else writeln(g,q div 2);
                 end;

   end;



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