var n,m,i:longint;
    multime:array[1..100005] of longint;
    r,x,q:longint;

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]=x then begin found:= true ; while multime[mid]=x do inc(mid); dec(mid); break end;
     if multime[mid]<x then  low:=mid
     else hight:=mid;
     if hight-low=1 then
      begin
       if multime[hight]=x then mid:=hight else
       if multime[low]=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]<=x then
     begin
        if x>=multime[hight] then begin mid:=hight;  break end
        else begin  while multime[mid]<=x do
                    inc(mid);
                 dec(mid);
                 break
                end;
        if hight-low=1 then
         begin
          if multime[hight]>x then mid:=low;
          break;
         end;
     end;
   if multime[mid]>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]>=x then begin while multime[mid]>=x do dec(mid); inc(mid); break end;
     if multime[mid]<x then low:=mid;
     if hight-low=1 then
     begin
      if multime[low]<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 i:=1 to n do read(multime[i]);
    readln(m);
     for i:=1 to m do
     begin
      readln(input,q,x);
      case 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.