// dfmt off
T lread(T=long)(){return readln.chomp.to!T;}T[] lreads(T=long)(long n){return iota(n).map!((_)=>lread!T).array;}
T[] aryread(T=long)(){return readln.split.to!(T[]);}void arywrite(T)(T a){a.map!text.join(' ').writeln;}
void scan(L...)(ref L A){auto l=readln.split;foreach(i,T;L){A[i]=l[i].to!T;}}alias sread=()=>readln.chomp();
void dprint(L...)(lazy L A){debug{auto l=new string[](L.length);static foreach(i,a;A)l[i]=a.text;arywrite(l);}}
alias PQueue(T,alias l="b<a")=BinaryHeap!(Array!T,l);import std, core.bitop;
// dfmt on
void main()
{
    auto input = stdin.byLine.map!split.joiner;

    long N;
    N = input.front.to!long;
    input.popFront;

    long Q;
    Q = input.front.to!long;
    input.popFront;

    long[] c = new long[](cast(size_t)(N));
    foreach (i; 0 .. cast(size_t)(N))
    {
        c[i] = input.front.to!long;
        input.popFront;
    }

    long[] l = new long[](cast(size_t)(Q));
    long[] r = new long[](cast(size_t)(Q));
    foreach (i; 0 .. cast(size_t)(Q))
    {
        l[i] = input.front.to!long;
        input.popFront;
        r[i] = input.front.to!long;
        input.popFront;
    }

    solve(N, Q, c, l, r);
}

void solve(long N, long Q, long[] c, long[] l, long[] r)
{
    auto bit = BinaryIndexedTree(N);
    auto last = new long[](5 * 100_000 + 1);
    auto I = iota(Q).array();
    zip(r, l, I).sort();
    auto ans = new long[](Q);
    long ptr = 0;
    foreach (i; 0 .. Q)
    {
        while (ptr < r[i])
        {
            // writefln("%s %s %s", ptr, c[ptr], last[0 .. 10]);
            bit.add(ptr + 1, 1);
            if (last[c[ptr]] != 0)
            {
                bit.add(last[c[ptr]], -1);
            }
            last[c[ptr]] = ptr + 1;
            ptr++;
        }
        // writefln("%s %s %s %s", I[i], l[i], r[i], last[0 .. 10]);
        ans[I[i]] = bit.sum(r[i]) - bit.sum(l[i] - 1);
    }
    foreach (a; ans)
    {
        writeln(a);
    }
}

/// BIT (1-indexed)
alias BinaryIndexedTree = BinaryIndexedTreeImpl!long;
struct BinaryIndexedTreeImpl(T)
{
    T[] _data;
    this(long n)
    {
        _data = new T[](n + 1);
    }

    T sum(long i)
    {
        T ans;
        for (; 0 < i; i -= (i & -i))
            ans += _data[i];
        return ans;
    }

    void add(long i, T x)
    {
        for (; i < _data.length; i += (i & -i))
            _data[i] += x;
    }
}
