var a, b, c, d:integer;
n, m: longint;
    sir: array [1..10000] of integer;
    prb: array [0..10000] of integer;
    sol: array [1..10000] of integer;
    i, j,  nr, poz, fc, k: integer;
    ok: boolean;
    f, g:text;
function max(i,j,nr:integer):integer;
begin
ok := false;
 while ((ok = false) and (i <= j)) do begin
  m := (i + j) div 2;
  if (sir[m] < nr) then i := m + 1;
  if (sir[m] > nr) then j := m - 1;
  if( sir[m] = nr) then ok := true;

  end;
  if( ok = true) then begin
    if (sir[m + 1] = nr) then
      while(sir[m + 1] = nr) do m := m + 1;
    max := m;
  end
  else max := -1;
end;
function mare(i, j, nr: integer): integer;
 begin
  ok := false;
 while ((ok = false) and (i <= j)) do begin
  m := (i + j) div 2;
  if (sir[m] < nr) then i := m + 1;
  if (sir[m] > nr) then j := m - 1;
  if( sir[m] = nr) then ok := true;

  end;
  if( ok = true) then begin
    if (sir[m+1] = nr) then
      while(sir[m+1] = nr) do m := m + 1;
    mare := m;
  end
  else mare := m;
 end;
 function mic(i, j, nr: integer): integer;
 begin
  ok := false;
 while ((ok = false) and (i <= j)) do begin
  m := (i + j) div 2;
  if (sir[m] < nr) then i := m + 1;
  if (sir[m] > nr) then j := m - 1;
  if( sir[m] = nr) then ok := true;

  end;
  if( ok = true) then begin
    if (sir[m+1] = nr) then
      while(sir[m+1] = nr) do m := m + 1;
    mic := m ;
  end
  else mic := m ;
 end;
begin
  assign(f, 'cautbin.in');
  reset(f);
  readln(f, n);
  for i := 1 to n do read(f, sir[i]);
  readln(f, m);

  assign(g, 'cautbin.out');
  rewrite(g);
  i := 1;
  j := n;

  for k := 1 to m  do begin
  read(f, c);
  readln(f, nr);
 fc := max(i, n, nr);
  poz := 0;
  if(c = 0) then poz := fc;
  if(c = 1) then begin
    if(fc = -1) then  poz := mare(i,n,nr)
    else poz := fc - 1;
  end;
  if(c = 2) then poz := mic(i,n,nr);

  writeln(g,poz);
  end;
  close(f);
  close(g);


end.