type kk=record
        q,x:longint;
        end;


var n,m,k:longint;
    multime:array[1..100005] of longint;
    r,x,q:longint;
    test:array[1..1000005] of kk;
function cautarebinara(low,hight:longint):longint;
var mid,i:longint;
   found:boolean;
begin
 found:=false;
  while low<hight do
   begin

     mid:=(hight+low) div 2;
     if multime[mid]=test[k].x then begin found:= true ; while multime[mid]=test[k].x do inc(mid); dec(mid); break end;
     if multime[mid]<test[k].x then  low:=mid
     else hight:=mid;
     if hight-low=1 then
      begin
       if multime[hight]=test[k].x then mid:=hight else
       if multime[low]=test[k].x then mid:=low  else mid:=-1;
      break
      end;
   end;
  if not(found) then cautarebinara:=-1
  else cautarebinara:=mid;

end;

function cautarebinara1(low,hight:longint):longint;
var mid,i:longint;
begin
 while low<hight do
  begin
    mid:=(hight+low) div 2;
   if multime[mid]<=test[k].x then
     begin
        if test[k].x>=multime[hight] then begin mid:=hight;  break end
        else begin  while multime[mid]<=test[k].x do
                    inc(mid);
                 dec(mid);
                 break
                end;
        if hight-low=1 then
         begin
          if multime[hight]>test[k].x then mid:=low;
          break;
         end;
     end;
   if multime[mid]>test[k].x then hight:=mid;

  end;
  cautarebinara1:=mid;
end;


function cautarebinara2(low,hight:longint):longint;
 var mid:longint;
 begin
   while low<=hight do
    begin

     mid:=(hight+low) div 2;
     if multime[mid]>=test[k].x then begin while multime[mid]>=test[k].x do dec(mid); inc(mid); break end;
     if multime[mid]<test[k].x then low:=mid;
     if hight-low=1 then
     begin
      if multime[low]<test[k].x then mid:=hight;
      break
     end;

    end;
    cautarebinara2:=mid;


 end;

begin
    assign(input,'cautbin.in'); reset(input);
    assign(output,'cautbin.out'); rewrite(output);
    readln(input,n);
    for k:=1 to n do read(multime[k]);
    readln(m);
     for k:=1 to m do readln(input,test[k].q,test[k].x);
     for k:=1 to m do
     begin
      case test[k].q of

        0: writeln(output,cautarebinara(1,n));
        1: writeln(output,cautarebinara1(1,n));
        2 :writeln(output,cautarebinara2(1,n));
      end;
     end;

    close(input);
    close(output);

end.