const maxn=100001;
type vector=array[0..maxn]of longint;
var n,i,m,x:longint;
    v:vector;
    tip:byte;

function caut0(var v:vector;var x:longint;p,q:longint):longint;
var r,s:longint;
begin
repeat
r:=(p+q)div 2;
s:=v[r];
if(s=x)and(v[r+1]<>x)then begin
                          caut0:=r;
                          exit;
                          end
                     else if x<s then q:=r-1
                                 else p:=r+1;
until p>q;
caut0:=-1;
end;

function caut1(var v:vector;var x:longint;p,q:longint):longint;
var r,s:longint;
begin
repeat
r:=(p+q)div 2;
s:=v[r];
if(s<=x)and(x<v[r+1])then begin
                          caut1:=r;
                          exit;
                          end
                     else if x<s then q:=r-1
                                 else p:=r+1;
until p>q;
caut1:=-1;
end;

function caut2(var v:vector;var x:longint;p,q:longint):longint;
var r,s:longint;
begin
repeat
r:=(p+q)div 2;
s:=v[r];
if(s>=x)and(x>v[r-1])then begin
                          caut2:=r;
                          exit;
                          end
                     else if x<=s then q:=r-1
                                  else p:=r+1;
until p>q;
caut2:=-1;
end;

begin
assign(input,'cautbin.in');
reset(input);
assign(output,'cautbin.out');
rewrite(output);
read(n);
v[0]:=-1;
for i:=1 to n do read(v[i]);
v[n+1]:=maxlongint;
read(m);
for i:=1 to m do
  begin
  read(tip,x);
  case tip of
    0:if x<>maxlongint then writeln(caut0(v,x,1,n))
                       else writeln(n);
    1:if x<>maxlongint then writeln(caut1(v,x,1,n))
                       else writeln(n);
    2:writeln(caut2(v,x,1,n));
    end;
  end;
close(output);
close(input);
end.