Program CautBin;

  var fi,fo:text;
      a:array[1..100000] of longint;
      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;

  if a[dr]=x then key:=dr
             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-1;

       end;
  key:=dr;

  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 dr:=pivot-1
                      else st:=pivot+1
                   end;
  key:=st;
  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
                        Caut0(x);
                        if i<>1 then Writeln(fo);
                        Write(fo,x);
                        end;
          if o=1 then begin

                                      Caut1(x);
                                                Writeln(fo);
                                                Write(fo,x);
                                  end;
          if o=2 then begin
                                                Caut2(x);
                                                Writeln(fo);
                                                Write(fo,x);
                                                end;
          o:=0;
                       end;

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