var v:array [1..100000] of longint;
    buf1:array [1..200000] of char;
    buf2:array [1..100000] of char;
    n, m, x, y, i, st, dr, p, max:longint;
    f, g:text;

begin
assign (f, 'cautbin.in'); settextbuf (f, buf1); reset (f);
assign (g, 'cautbin.out'); settextbuf (g, buf2); rewrite (g);
read (f, n); for i := 1 to n do read (f, v[i]);
read (f, m);
for i := 1 to m do
  begin
  read (f, x, y);
  st:=1; dr:=n;
  case x of
  0:begin
    max:=-1;
    while st<=dr do
      begin
      p:= st+ (dr-st) div 2;
      if v[p]<y then st:=p+1;
      if v[p]>y then dr:=p-1;
      if v[p]=y then begin max:=p; st:=p+1; end;
      end;
    writeln (g, max);
    end;
  1:begin
    while st<=dr do
      begin
      p:= st+ (dr-st) div 2;
      if v[p]<=y then
        begin
        st:=p+1;
        max:=p;
        end
                else
        begin
        dr:=p-1;
        end;
      end;
    writeln (g, max);
    end;
  2:begin
    while st<=dr do
      begin
      p:= st+ (dr-st) div 2;
      if v[p]>=y then
        begin
        dr:=p-1;
        max:=p;
        end
                else
        begin
        st:=p+1;
        end;
      end;
    writeln (g, max);
    end;
  end;
  end;

close (f); close (g);
end.