Program bs123;
var i,k,m,n,h,p:longint;
    a:array[1..100005] of longint;
    f,q:text;
function bs1(var st,dr,p:longint):longint;
var mid:longint;
    ok:boolean;
begin
ok:=false;
if p=a[n] then begin ok:=true; bs1:=n; end;
        while (st<dr) and (ok=false) do
        begin
        mid:=((st+dr) div 2);
                if p>a[mid] then st:=mid+1
                else if p<a[mid] then dr:=mid-1
                else if p=a[mid] then
                begin
                        if a[mid+1]=p then st:=mid+1
                        else if (a[mid+1]>p) or (mid=n) then begin ok:=true; bs1:=mid; end;
                end;
        end;
if st>=dr then bs1:=-1;

end;
function bs2(var st,dr,p:longint):longint;
var mid:longint;
    ok:boolean;
begin
ok:=false;
if p=a[n] then begin ok:=true; bs2:=n; end;
        while (st<dr) and (ok=false) do
        begin
                mid:=((st+dr) div 2);
                if p<a[mid] then dr:=mid-1
                else if (a[mid]<=p) and (a[mid+1]<=p) and (mid+1<n) then st:=mid+1
                else if (a[mid]<=p) and (a[mid+1]>p) then begin bs2:=mid; ok:=true; end;
        end;
end;
function bs3(var st,dr,p:longint):longint;
var mid:longint;
    ok:boolean;
begin
ok:=false;
if a[1]>=p then begin ok:=true; bs3:=1; end;
        while (st<dr) and (ok=false) do
        begin
                mid:=(st+dr) div 2;
                if a[mid]<p then st:=mid+1
                else if (a[mid]>=p) and (a[mid-1]>=p) and (mid-1>0) then dr:=mid-1
                else if (a[mid]=p) and (a[mid-1]<p) then begin ok:=true; bs3:=mid; end;
        end;
if st=dr then bs3:=st;
end;
begin
assign(f,'cautbin.in');
reset(f);
assign(q,'cautbin.out');
rewrite(q);
readln(f,n);
for i:=1 to n do read(f,a[i]);
read(f,m);
for i:=1 to m do
begin
        h:=1;
        readln(f,k,p);
        if k=0 then writeln(q,bs1(h,n,p))
        else if k=1 then writeln(q,bs2(h,n,p))
        else if k=2 then writeln(q,bs3(h,n,p));
end;
close(f);
close(q);
end.