var niz: array[1..100000] of longint;
    ma: array[0..3000,0..3000] of longint;
    b: array[1..3000,1..3000] of boolean;
    i,j,x,y,n,m,t,p,k: longint;
begin
     assign(input,'knjige.in');
     reset(input);
     assign(output,'knjige.out');
     rewrite(output);
     readln(n,k);
     for i:=1 to n do
      begin
       read(niz[i]);
       ma[i,i]:=1;
       b[i,niz[i]]:=true;
      end;
     readln;
     for i:=1 to n-1 do
      begin
       for j:=i+1 to n do
        if not b[i,niz[j]] then
         begin
          b[i,niz[j]]:=true;
          ma[i,j]:=ma[i,j-1]+1;
         end
        else ma[i,j]:=ma[i,j-1];
      end;
     for i:=1 to k do
      begin
       readln(x,y);
       writeln(ma[x,y]);
      end;
     close(input);
     close(output);
end.