program binco;
var s:array[1..100000] of longword; n,m,i,key:longword; f,g:text; ind:byte;

function caut0(st,dr,key:longword):longint;
var mid:word;
begin
if st>dr then caut0:=-1
else begin
        mid:=(st+dr) div 2;
        if s[mid]=key then
                begin
                if caut0(mid+1,dr,key)>-1 then caut0:=caut0(mid+1,dr,key)
                else caut0:=mid;
                end
        else if (key<s[mid]) then caut0:=caut0(st,mid-1,key)
        else caut0:=caut0(mid+1,dr,key)
        end;
end;

function caut1(st,dr,key:longword):longword;
var mid:word;
begin
if st>dr then caut1:=0
else begin
        mid:=(st+dr) div 2;
        if s[mid]<=key then
                begin
                caut1:=mid;
                if caut1(mid+1,dr,key)>mid then caut1:=caut1(mid+1,dr,key);
                end
        else caut1:=caut1(st,mid-1,key);
        end
end;

function caut2(st,dr,key:longword):longword;
var mid:word;  loc:longword;
begin
if st>dr then caut2:=0
else begin
        mid:=(st+dr) div 2;
        if s[mid]>=key then
                begin
                caut2:=mid;
                loc:=caut2(st,mid-1,key);
                if (loc<mid) and (loc>0) then caut2:=caut2(st,mid-1,key)
                end
        else caut2:=caut2(mid+1,dr,key);
        end
end;

begin
assign(f,'cautbin.in'); reset(f);
assign(g,'cautbin.out'); rewrite(g);
readln(f,n);
for i:=1 to n do
        read(f,s[i]);
readln(f,m);
for i:=1 to m do
        begin
        readln(f,ind,key);
        if ind=0 then writeln(g,caut0(1,n,key))
        else if ind=1 then writeln(g,caut1(1,n,key))
        else writeln(g,caut2(1,n,key));
        end;
close(f); close(g);
end.