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,mr: 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);
 mr := mare(i,j,nr);
  poz := 0;
  if(c = 0) then poz := fc;
  if(c = 1) then begin
    if(fc = -1) then  begin
      if((sir[mr] < nr) and (sir[mr + 1] > nr)) then poz := mr;
      if(sir[mr] > nr) then poz := mr - 1;
      if((sir[mr + 1] < nr) and (sir[mr + 2] > nr)) then poz := mr + 1;
       end
    else poz := fc ;
  end;
  if(c = 2) then begin
    if(fc = -1) then begin
      if(sir[mr] > nr) then poz := mr
      else poz := mr + 1;
    end

    else poz := fc;
  end;
  writeln(g,poz);
  end;
  close(f);
  close(g);


end.