program cb;
var n,m:integer;
    a:byte;
    b:longint;
    v:array[0..100000] of longint;
    f,g:text;

procedure fisier;
begin
 assign (f,'cautbin.in');
 assign (g,'cautbin.out');
 reset(f);
 rewrite(g);
end;

function search0(x:longint):longint;
var st,dr,mij,max:longint;
begin
 max:=-1;
 st:=1;
 dr:=n;
 while st<=dr do
  begin
   mij:=st + (dr-st) div 2;
   if x<v[mij] then dr:=mij-1
   else if v[mij]<x then st:=mij+1
   else begin max:=mij;st:=mij+1;end;
  end;
 search0:=max;
end;

function search1(x:longint):longint;
var st,dr,mij,max:longint;
begin
 st:=1;
 dr:=n;
 while st<=dr do
  begin
   mij:=st + (dr-st) div 2;
   if v[mij]<=x then begin st:=mij+1; max:=mij; end
   else dr:=mij-1;
  end;
 search1:=max;
end;

function search2(x:longint):longint;
var st,dr,mij,min:longint;
begin
 min:=n+1;
 st:=1;
 dr:=n;
 while st<=dr do
  begin
   mij:=st + (dr-st) div 2;
   if v[mij]>=x then begin dr:=mij-1;min:=mij; end
   else st:=mij+1;
  end;
 search2:=min;
end;

procedure citire;
var i:integer;
begin
 readln(f,n);
 for i:=1 to n do
  read(f,v[i]);
 readln(f);
end;

procedure solve;
begin
 readln(f,m);
 while (m<>0) do
  begin
   readln(f,a,b);
   case a of
   0:writeln(g,search0(b));
   1:writeln(g,search1(b));
   2:writeln(g,search2(b));
   end;
   dec(m);
  end;
end;

begin
 fisier;
 citire;
 solve;
 close(f);
 close(g);
end.