program cautabin;
var A:array[1..100000] of longint;
n,m: longint;
k: byte;
t,l,x,s,d: longint;
i,j: longint;

function cb1:longint;
begin
  cb1:=-1; s:=1;d:=n;
  while (s<=d) do
  begin
    t:=s+(d-s) shr 1;
    if A[t]>x then d:=t-1
    else
    if A[t]<x then s:=t+1
    else
    begin
      cb1:=t;
      exit;
    end;
  end;
end;

function cb2:longint;
begin
  l:=0; s:=1; d:=n;
  while (s<=d) do
  begin
    t:=s+(d-s) shr 1;
    if A[t]<=x then
    begin
      l:=t;
      s:=t+1;
    end
    else d:=t-1;
  end;
  cb2:=l;
end;

function cb3:longint;
begin
  l:=n+1; s:=1; d:=1;
  while (s<=d) do
  begin
    t:=s+(d-s) shr 1;
    if A[t]>=x then
    begin
      l:=t;
      d:=d-1;
    end
    else
    s:=t+1;
  end;
  cb3:=l;
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(k,x);
    if k=0 then
     writeln(cb1)
    else
    if k=1 then
     writeln(cb2)
    else
     writeln(cb3);
  end;

  close(input);
  close(output);
end.