var f,g:Text;
    p,n,c,x,m,i,k:longint;
    a,b:array[1..5000]of longint;
function caut_bin(x:longint):longint;
         var s,d,mij:longint;
         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;
                    {if (c=0)and(a[mij]=x)then begin
                                              writeln(g,mij);
                                              break;
                                              end
                    else if (c=1)and(a[mij]<x)then begin
                                                   writeln(g,mij);
                                                   break;
                                                   end
                    else if (c=2)and(a[mij]>x)then begin
                                                   writeln(g,mij);
                                                   break;
                                                   end
                    else if c=0 then begin
                                     if a[mij]<x then s:=mij+1
                                     else d:=mij-1;
                                     end
                    else if c=1 then begin
                                     d:=mij-1;
                                     end
                    else if c=2 then begin
                                     s:=mij+1;
                                     end; }
                    end;
              caut_bin:=d
         end;


begin
assign(f,'cautbin.in');reset(f);
assign(g,'cautbin.out');rewrite(g);
readln(f,n);
{for i:=1 to n do
    read(f,a[i]);}
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.