var v:array[1..100000] of longint;
    nr,n,m,i:longint;
    k:byte;
    f,g:text;

function bs(k:byte; val:longint):longint;
var i,step:longint;
begin
  step:=1; i:=0;
  while step<n do step:=step shl 1;
  while step>0 do
    begin
      if (v[i+step]<=val) and (i+step<=n) then inc(i,step);
      step:=step shr 1;
    end;
  if v[i]=val then bs:=i
  else
    case k of
      0:bs:=-1;
      1:bs:=i;
      2:bs:=i+1;
    end;
end;

begin
  assign(f,'cautbin.in');
  reset(f);
  assign(g,'cautbin.out');
  rewrite(g);
  readln(f,n);
  for i:=1 to n do read(f,v[i]);
  readln(f,m);
  for i:=1 to m do
    begin
      readln(f,k,nr);
      writeln(g,bs(k,nr));
    end;
  close(f);
  close(g);
end.