type vector=array[1..100000] of longint;
var n,m,a,o,k,i,x:longint;
    v:vector;
    fin,fout:text;
    gasit:boolean;


procedure cbin(n,x:longint;
              v:vector;
              var k,o:longint);
var li,ls:longint;
    gasit:boolean;
begin
li:=1;
ls:=n;
gasit:=false;
repeat
    k:=li +(ls-li) div 2;
    if v[k]=x then
       gasit:=true
       else
       if v[k]<x then
          li:=k+1
          else
          ls:=k-1;
until (li>ls) or gasit;
if li>ls then
   o:=-1;
end;



begin
assign(fin,'cautbin.in');
assign(fout,'cautbin.out');
reset(fin);
rewrite(fout);
read(fin,n);
for i:=1 to n do
    read(fin,v[i]);
read(fin,m);
for i:=1 to m do
    begin
    read(fin,a,x);
    cbin(n,x,v,k,o);
    if a=0 then
       if o=-1 then
          writeln(fout,'-1')
          else
          begin
          while v[k]=x do
                inc(k);
          writeln(fout,k-1);
          end
       else
           if a=1 then
              begin
              while v[k]<=x do
                    inc(k);
              writeln(fout,k-1);
              end else
                  if a=2 then
                     begin
                     while v[k]>=x do
                           dec(k);
                     writeln(fout,k+1);
                     end;

    end;
close(fin);
close(fout);
end.