var a:array [0..100001] of cardinal;
n,lp,rp,c:integer;

procedure rd;
var i:integer;
begin
  read(n);
  a[0]:=-1;
  a[n+1]:=2147483648;
  for i:=1 to n do
    read(a[i]);
end;

function zero(l,r:integer):integer;
var y:integer;
begin
  if ((a[l]=c) and (a[l+1]>c)) then zero:=l else
  if ((a[r]=c) and (a[r+1]>c)) then zero:=r else
  if ((lp=l) and (rp=r)) then zero:=-1 else
  begin
    y:=(l+r) div 2;
    lp:=l; rp:=r;
    if (a[y]>c) then zero:=zero(l,y) else zero:=zero(y,r);
  end;
end;

function unu(l,r:integer):integer;
var y:integer;
begin
  if ((a[l]<=c) and (a[l+1]>c)) then unu:=l else
  if ((a[r]<=c) and (a[r+1]>c)) then unu:=r else
  if ((lp=l) and (rp=r)) then unu:=-1 else
  begin
    y:=(l+r) div 2;
    lp:=l; rp:=r;
    if (a[y]>c) then unu:=unu(l,y) else unu:=unu(y,r);
  end;
end;

function doi(l,r:integer):integer;
var y:integer;
begin
  if ((a[l]>=c) and (a[l-1]<c)) then doi:=l else
  if ((a[r]>=c) and (a[r-1]<c)) then doi:=r else
  if ((lp=l) and (rp=r)) then doi:=-1 else
  begin
    y:=(l+r) div 2;
    lp:=l; rp:=r;
    if (a[y]>=c) then doi:=doi(l,y) else doi:=doi(y,r);
  end;
end;

procedure solve;
var i,x,m:integer;
begin
  read(m);
  for i:=1 to m do
  begin
    lp:=-1; rp:=-1;
    read(x,c);
    if (x=0) then writeln(zero(1,n));
    if (x=1) then writeln(unu(1,n));
    if (x=2) then writeln(doi(1,n));
  end;
end;

begin
  assign(input,'cautbin.in');
  assign(output,'cautbin.out');
  rd;
  solve;
end.