var f,g:Text;
    p,n,c,x,m,i,k:longint;
    a,b:array[1..100000]of longint;
function caut_bin(x:longint):longint;
         var s,d,mij:int64;
         begin
              s:=1;d:=k;
              while (s<=d) do
                    begin
                    mij:=(s+d) div 2;
                    if a[mij]=x then begin d:=mij; break end
                       else if a[mij]>x then d:=mij-1
                            else s:=mij+1;
                    end;
              caut_bin:=d
         end;
begin
assign(f,'cautbin.in');reset(f);
assign(g,'cautbin.out');rewrite(g);
readln(f,n);
read(f,a[1]); b[1]:=1; k:=1;
for i:=2 to n do
    begin
       read(f,x);
       if x<>a[k] then begin k:=k+1; a[k]:=x; b[k]:=i end
    end;
readln(f,m);
for i:=1 to m do
    begin
    read(f,c,x);
    p:=caut_bin(x);
    case c of
       0: if a[p]=x then if p=k then writeln(g,n)
                            else writeln(g,b[p+1]-1)
             else writeln(g,-1);
       1: writeln(g,b[p]);
       2: if a[p]=x then writeln(g,b[p])
             else writeln(g,b[p]+1)
    end;
    end;
close(g);
end.