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


begin
  assign(input,'cautbin.in');
  reset(input);
  assign(output,'cautbin.out');
  rewrite(output);
  readln(n);
  for i:=1 to n do
   read(A[i]);
  readln;
  readln(m);
  for i:=1 to m do
  begin
    readln(k,x);
    case k of
    0:
begin
  cb:=-1; s:=1; d:=n;
  while (s<=d) do
  begin
    t:=s+(d-s) div 2;
    if A[t]>x then d:=t-1
    else
    if A[t]<x then s:=t+1
    else
    begin
      cb:=t;
      break;
    end;
  end;
  writeln(cb);
end;

    1:
begin
  cb:=0; s:=1; d:=n;
  while (s<=d) do
  begin
    t:=s+(d-s) div 2;
    if A[t]<=x then
    begin
      cb:=t;
      s:=t+1;
    end
    else d:=t-1;
  end;
  writeln(cb);
end;

    2:
begin
  cb:=n+1; s:=1; d:=n;
  while (s<=d) do
  begin
    m:=s+(d-s) div 2;
    if A[m]>=x then
    begin
      cb:=m;
      d:=d-1;
    end
    else
    s:=m+1;
  end;
  writeln(cb);
end;

    end;{case}
  end;
  close(input);
  close(output);
end.