program cautbin;
  var n,m,x,i,r:longint;
      a:array[1..100000] of  longint;

function cb(r,x:longint):longint;
 var i,j,m:longint;
 begin
   i:=1;
   j:=n;
   cb:=1;
   while i<=j do
     begin
       m:=(i+j) div 2;
       case r of

       0: begin if x=a[m] then begin cb:=m; i:=m+1; end
                      else if x>a[m] then i:=m+1
                          else j:=m-1;
            end;
       1: begin if x>=a[m] then begin cb:=m; i:=m+1; end
                          else j:=m-1;
            end;
       2: begin if x<=a[m] then begin cb:=m; j:=m-1 end
                          else i:=m+1;
            end;
       end;
   end;
end;

begin
  assign(input,'cautbin.in'); reset(input);
  assign(output,'cautbin.out'); rewrite(output);
  readln(n);
  for i:=1 to n do read(a[i]);
  readln(m);
  for i:=1 to m do
    begin
      readln(r,x);
      writeln(cb(r,x));
    end;
  close(output);
end.