program binarsearch;
type vector1=array[0..100001] of longint;
var t:vector1;
    n,i,tip,x,m:longint;
    f1,f2:text;
function cauta1(st,dr,x:longint):longint;
var m,sol:longint;
begin
sol:=-1;
while st<=dr do begin
m:=(st+dr) div 2;
if t[m]=x then sol:=m;
if t[m]>x then dr:=m-1 else st:=m+1;
end;
cauta1:=sol;
end;
function cauta2(st,dr,x:longint):longint;
var m,sol:longint;
begin
sol:=0;
while (st<=dr) do begin
m:=(st+dr) div 2;
if t[m]<=x then begin
sol:=m;
st:=m+1;
end else dr:=m-1;
end;
cauta2:=sol;
end;
function cauta3(st,dr,x:longint):longint;
var m,sol:longint;
begin
sol:=0;
while (st<=dr) do begin
m:=(st+dr) div 2;
if t[m]>=x then begin
sol:=m;
dr:=m-1;
end else st:=m+1;
end;
cauta3:=sol;
end;
begin
assign (f1,'cautbin.in');
assign (f2,'cautbin.out');
reset (f1);
rewrite (f2);
readln (f1,n);
for i:=1 to n do read (f1,t[i]);
readln (f1,m);
for i:=1 to m do begin
readln (f1,tip,x);
if tip=0 then writeln (f2,cauta1(1,n,x)) else
if tip=1 then writeln (f2,cauta2(1,n,x)) else
writeln (f2,cauta3(1,n,x));
end;
close (f1);
close (f2);
end.