var n,m,i,c,x:longint;
    a:array[1..100000] of longint;
    
function bin0(x:longint):longint;
var m,s,d:longint;
begin
  s:=1;
  d:=n;
  while s<d do begin
    m:=(s+d) div 2;
    if a[m]<=x then
      s:=m+1
    else 
      d:=m;
  end;
  bin0:=-1;
  if a[s]=x then 
    bin0:=s
  else
    if a[s-1]=x then
      bin0:=s-1;
end;

function bin1(x:longint):longint;
var m,s,d:longint;
begin
  s:=1;
  d:=n;
  while s<d do begin
    m:=(s+d) div 2;
    if a[m]<=x then
      s:=m+1
    else 
      d:=m;
  end;
  if a[s]<=x then
    bin1:=s
  else 
    bin1:=s-1;
end;

function bin2(x:longint):longint;
var m,s,d:longint;
begin
  s:=1;
  d:=n;
  while s<d do begin
    m:=(s+d) div 2;
    if a[m]<x then
      s:=m+1
    else 
      d:=m;
  end;
  bin2:=s
end;
    
begin
  assign(input,'cautbin.in');
  reset(input);
  assign(output,'cautbin.out');
  rewrite(output);
  read(n);
  for i := 1 to n do
    read(a[i]);
  read(m);
  for i:=1 to m do begin
    read(c, x);
    if c=0 then writeln(bin0(x));
    if c=1 then writeln(bin1(x));
    if c=2 then writeln(bin2(x));
  end;
     
end.