var a:array[1..100003]of longint;
    n,m,i,x,rez:longint;
    tip:byte;
    f,fo:text;
function cbin0(st,dr,x:longint):longint;
var m:longint;
begin
while st<dr do
begin
m:=st+(dr-st)div 2;
 if x<a[m] then dr:=m
           else if x>a[m] then st:=m+1
                          else begin
                                cbin0:=m;
                                st:=m+1
                               end
end;
if a[st]=x then cbin0:=st;
end;
function cbin1(st,dr,x:longint):longint;
var m:longint;
begin
 while st<dr do
 begin
 m:=st+(dr-st)div 2;
  if x<a[m] then dr:=m
            else
             begin
              cbin1:=m;
              st:=m+1
             end
 end;
if a[st]<=x then cbin1:=st;
end;

function cbin2(st,dr,x:longint):longint;
var m:longint;
begin
while st<dr do
 begin
 m:=st+(dr-st)div 2;
 if x>a[m] then st:=m+1
           else
            begin
             cbin2:=m;
             dr:=m
            end
 end;
if a[st]>=x then cbin2:=st;
end;

begin
assign(f,'cautbin.in');
assign(fo,'cautbin.out');
reset(f);
readln(f,n);
for i:=1 to n do
 read(f,a[i]);
readln(f);
readln(f,m);
rewrite(fo);
for i:=1 to m do
 begin
  readln(f,tip,x);
  rez:=-1;
  case tip of
   0:rez:=cbin0(1,n,x);
   1:rez:=cbin1(1,n,x);
   2:rez:=cbin2(1,n,x);
  end;
 writeln(fo,rez);
 end;
close(fo);
close(f);
end.