program pascal;
var f,g:text;
    st,dr,i,n,p,q,t,m,pos: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;
                      repeat
                          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;
                                                 pos:=q div 2;
                                               end;
                       until (ok) or (st+1=dr);
                       if st+1=dr then
                            begin
                             if p=v[st] then
                                        begin
                                         ok:=true;
                                         pos:=st;
                                         end
                                        else
                              if p=v[dr] then
                                       begin
                                        ok:=true;
                                        pos:=dr;
                                        end;
                             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);
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,pos)
                     else writeln(g,-1);
              end;
     if t=1 then begin
                    florin;
                    if ok then writeln(g,pos)
                          else writeln(g,st);
                  end;
     if t=2 then begin
                    florin;
                    if ok then writeln(g,pos)
                         else writeln(g,dr);
                 end;

   end;



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