Program CautBin;

  var fi,fo:text;
      a:array[1..100000] of integer;
      n,m,i:1..100000;
      x,o:integer;

  Procedure Caut0(var key:integer);
   var st,dr,pivot:1..100000;

  begin
  st:=1; dr:=n;
  While st<=dr do begin
     pivot:=(st+dr) div 2;
      if a[pivot]<=key then st:=pivot+1
                       else dr:=pivot-1;

       end;

  pivot:=(st+dr) div 2;
  if (a[pivot+1]=key) then key:=pivot+1


               else if a[pivot]=key then key:=pivot
                                    else key:=-1;


  end;


  Procedure Caut1(var key:integer);
   var st,dr,pivot:1..100000;

  begin
  st:=1; dr:=n;
  While st<dr do begin
     pivot:=(st+dr) div 2;
      if a[pivot]<=key then st:=pivot+1
                       else dr:=pivot;

       end;

  pivot:=(st+dr) div 2;
  if a[pivot]>key then key:=pivot-1;



  end;


  Procedure Caut2(var key:integer);
   var st,dr,pivot:1..100000;

  begin
  st:=1; dr:=n;
  While st<dr do begin
     pivot:=(st+dr) div 2;
      If a[pivot]<key then st:=pivot+1
                      else dr:=pivot
                   end;

  if a[pivot]<key then key:=pivot+1;
  end;

  begin
   assign(fi,'cautbin.in');
   assign(fo,'cautbin.out');
   reset(fi);rewrite(fo);
   Readln(fi,n);
   For i:=1 to n do
   Read(fi,a[i]);
   readln(fi);
   Read(fi,m);
   For i:=1 to m do begin
         read(fi,o); read(fi,x);
         if o=0 then begin
                        if x<a[1] then x:=-1
                                  else
                                        Caut0(x);
                        Writeln(fo,x);
                        end
                 else if o=1 then begin

                                      if x>a[n] then x:=n
                                                else Caut1(x);
                                                Writeln(fo,x);
                                  end
                             else if o=2 then begin
                                                Caut2(x);
                                                Writeln(fo,x);
                                                end;

                       end;

  close(fi);close(fo);
end.