program caut;
var a:array[0..100000] of longint;
    b:array[1..1 shl 15] of char;
    n,m,i,k,x:longint;
function search0(p,u,k:longint):longint;
var m:longint;
begin
while p<=u do begin
              m:=(p+u)div 2;
              if a[m]<=k then p:=m+1
                         else u:=m-1;
              end;
m:=(p+u) div 2;
if a[m]=k then search0:=m
          else search0:=-1;
end;

function search1(p,u,k:longint):longint;
var m:longint;
begin
while p<=u do begin
              m:=(p+u) div 2;
              if a[m]<=k then p:=m+1
                         else u:=m-1;
              end;
m:=(p+u) div 2;
search1:=m;
end;

function search2(p,u,k:longint):longint;
var m:longint;
begin
while p<u do begin
             m:=(p+u) div 2;
             if a[m]<k then p:=m+1
                       else u:=m;
             end;
m:=(p+u)div 2;
search2:=m;
end;

begin
assign(input,'cautbin.in'); settextbuf(input,b); reset(input);
assign(output,'cautbin.out'); rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
readln(m);
for i:=1 to m do begin
                 readln(x,k);
                 if x=0 then writeln(search0(1,n,k));
                 if x=1 then writeln(search1(1,n,k));
                 if x=2 then writeln(search2(1,n,k));
                 end;
close(output);
end.