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

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

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

function caut2(st,dr,key:longint):longint;
var mid:longint;
begin
while (st<=dr) do
        begin
        mid:=(st+dr) div 2;
        if s[mid]<key then st:=mid+1
        else dr:=mid-1;
        end;
caut2:=st;
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);
readln;
end.