program cautbin;
var f,g:text;
    a:array[1..100000] of integer;
    n,m,i,x,nr:longint;

function c0(st,dr:longint;x:integer):longint;
var m:longint;
begin
if st=dr then
  if a[st]=x then c0:=st
  else
else begin
  m:=(st+dr) div 2;
  if a[m]<x then c0:=c0(m+1,dr,x)
  else c0:=c0(st,m,x);
  end;

end;

function cc0(x:integer):longint;
var i:integer;
begin
i:=c0(1,n,x);
repeat
  inc(i);
until (a[i]>x) or (i=n+1);
cc0:=i-1;
end;

function c1(st,dr:longint; x:integer):longint;
var m:longint;
begin
if st=dr then
  if (a[st]<=x) and ((a[st+1]>x) or (st=n)) then c1:=st
  else
else begin
  m:=(st+dr) div 2;
  if a[m]>x then c1:=c1(st,m-1,x)
  else
    if (a[m]<=x) and ((a[m+1]>x) or (m=n)) then c1:=m
    else
      if a[m+1]<=x then c1:=c1(m+1,dr,x);
  end;
end;

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

begin
assign(f,'cautbin.in');
assign(g,'cautbin.out');
reset(f);
rewrite(g);
readln(f,n);
for i:=1 to n do read(f,a[i]);
readln(f,m);
for i:=1 to m do begin
  readln(f,nr,x);
  case nr of
  0:writeln(g,cc0(x));
  1:writeln(g,c1(1,n,x));
  2:writeln(g,c2(1,n,x));
  end;
  end;
close(g);
end.