var x,n,m,i,q:longint;
    v:array[0..100001] of longint;
    o,f:text;
    buff,bufo:array[1..1 shl 18] of char;
function bsr0(s,d,p:longint):longint;
var m:longint;
  begin
    m:=(s+d)div 2;bsr0:=-1;
    if s<=d then
      if (v[m]=p)and((v[m+1]>v[m])or(m=n)) then bsr0:=m
                                  else if v[m]>p then bsr0:=bsr0(s,m-1,p)
                                                 else bsr0:=bsr0(m+1,d,p);

  end;
function bsr1(s,d,p:longint):longint;
var m:longint;
  begin
    m:=(s+d)div 2;bsr1:=-1;
    if s<=d then
      if (v[m]<=p)and((v[m+1]>p)or(m=n)) then bsr1:=m
                                else if v[m]>p then bsr1:=bsr1(s,m-1,p)
                                               else bsr1:=bsr1(m+1,d,p);

  end;
function bsr2(s,d,p:longint):longint;
var m:longint;
  begin
    m:=(s+d)div 2;bsr2:=-1;
    if s<=d then
      if (v[m]>=p)and(v[m-1]<p) then bsr2:=m
                                else if v[m]<p then bsr2:=bsr2(m+1,d,p)
                                               else bsr2:=bsr2(s,m-1,p);

  end;
begin
assign(o,'cautbin.out');assign(f,'cautbin.in');
settextbuf(f,buff);settextbuf(o,bufo);
reset(f);rewrite(o);
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,q);read(f,x);
    case q of
      0:writeln(o,bsr0(1,n,x));
      1:writeln(o,bsr1(1,n,x));
      2:writeln(o,bsr2(1,n,x));
    end;
  end;
close(o);close(f);
end.