Program binarx3;
var a:array[1..100009] of integer;
    m,n,i,x,k,h:integer;
    f,q:text;
function bs1(var st,dr,p:integer):integer;
var mid,aux:integer;
begin
        mid:=((st+dr) div 2);
        if st>dr then bs1:=-1;
        if p>a[mid] then
        begin
                    st:=mid+1;
                    bs1:=bs1(st,dr,p);
        end

                    else if p<a[mid] then
                    begin
                        dr:=mid-1;
                        bs1:=bs1(st,dr,p);
                    end;
        if p=a[mid] then
        begin
                if a[mid+1]=p then
                begin
                        st:=mid+1;
                        bs1:=bs1(st,dr,p);
                end;
                if a[mid+1]>p then bs1:=mid;
                if mid=n then bs1:=mid;
        end;
end;
function bs2(var st,dr,p:integer):integer;
var mid:integer;
begin
        mid:=(st+dr) div 2;
        if p<a[mid] then
        begin
                dr:=mid-1;
                bs2:=bs2(st,dr,p);
        end
                else
        begin
                if (a[mid]=p) and (a[mid+1]=p) and (mid+1<n) then
                begin
                        st:=mid+1;
                        bs2:=bs2(st,dr,p);
                end
                else if (a[mid]=p) and (a[mid+1]>p) then bs2:=mid
                else if mid=n then bs2:=mid;
        end;
end;
function bs3(var st,dr,p:integer):integer;
var mid:integer;
begin
        mid:=(st+dr) div 2;
        if a[mid]<p then
        begin
                st:=mid+1;
                bs3:=bs3(st,dr,p);
        end
                else
        begin
                if (a[mid]=p) and (a[mid-1]=p) and (mid-1>0) then
                begin
                        dr:=mid-1;
                        bs3:=bs3(st,dr,p);
                end
                else if (a[mid]=p) and (a[mid-1]<p) then bs3:=mid
                else if mid=n then bs3:=mid
                else if a[1]>=p then bs3:=1;
        end;
end;


begin
assign(f,'cautbin.in');
reset(f);
assign(q,'cautbin.out');
rewrite(q);
read(f,n);
for i:=1 to n do read(f,a[i]);
read(f,m);
for i:=1 to m do
begin
        read(f,k,x);
        h:=1;
        if k=0 then writeln(q,bs1(h,n,x));
        if k=1 then writeln(q,bs2(h,n,x));
        if k=2 then writeln(q,bs3(h,n,x));
end;
close(f);
close(q);
end.