const maxn=100000;
type vector=array[1..maxn]of longint;
var n,m,i,x,p,q,r,s:longint;
    t:byte;
    v:vector;

function caut0:longint;
begin
p:=1;
q:=n;
repeat
r:=(p+q)div 2;
s:=v[r];
if(s=x)and((r=n)or(v[r+1]<>x))then begin
                                   caut0:=r;
                                   exit;
                                   end
                              else if x<s then q:=r-1
                                          else p:=r+1;
until p>q;
caut0:=-1;
end;

function caut1:longint;
begin
p:=1;
q:=n;
repeat
r:=(p+q)div 2;
if x<v[r]then q:=r-1
         else begin
              caut1:=r;
              p:=r+1;
              end;
until p>q;
end;

function caut2:longint;
begin
p:=1;
q:=n;
repeat
r:=(p+q)div 2;
if x<=v[r]then begin
               caut2:=r;
               q:=r-1;
               end
        else p:=r+1;
until p>q;
end;

begin
assign(input,'cautbin.in');
reset(input);
assign(output,'cautbin.out');
rewrite(output);
read(n);
for i:=1 to n do read(v[i]);
read(m);
for i:=1 to m do
  begin
  read(t,x);
  case t of
    0:writeln(caut0);
    1:writeln(caut1);
    2:writeln(caut2);
    end;
  end;
close(output);
close(input);
end.