Program Cautbin;
var Intrare,Iesire : text;
    op : byte;
    n,m,i,x : longint;
    A : array[1..100000] of longint;

function poz(op : byte; x,lo,hi : longint) : longint;
var mid,v : longint;
begin
  mid:=lo+(hi-lo) div 2;
  case op of
   0: begin
     if lo=hi then begin
       if A[lo]=x then poz:=lo else poz:=-1;
     end
     else begin
       if x>=A[mid] then begin
         v:=poz(0,x,mid+1,hi);
         if x=A[mid] then
          if v>-1 then poz:=v else poz:=mid
         else poz:=v;
       end
       else poz:=poz(0,x,lo,mid);
     end;
   end;

   1: begin
     if lo=hi then begin
       if A[lo]<=x then poz:=lo else poz:=-1;
     end
     else begin
       if x>=A[mid] then begin
         v:=poz(1,x,mid+1,hi);
         if v>-1 then poz:=v else poz:=mid
       end
       else poz:=poz(1,x,lo,mid);
     end;
   end;

   2: begin
     if lo=hi then begin
       if A[lo]>=x then poz:=lo else poz:=-1;
     end
     else begin
       if x<=A[mid] then begin
         v:=poz(2,x,lo,mid);
         if v>-1 then poz:=v else poz:=mid
       end
       else poz:=poz(2,x,mid+1,hi);
     end;
   end;
  end;
end;

begin
  assign(Intrare,'cautbin.in');
  reset(Intrare);
  readln(Intrare,n);
  for i:=1 to n do read(Intrare,A[i]);
  assign(Iesire,'cautbin.out');
  rewrite(Iesire);
  readln(Intrare,m);
  for i:=1 to m do begin
    readln(Intrare,op,x);
    writeln(Iesire,poz(op,x,1,n));
  end;
  close(Iesire);
  close(Intrare);
end.