#include<bits/stdc++.h>

#define ll long long
#define rep(A,B,C) for(A=B;A<C;++A)
#define pii pair<int,int>
#define pll pair<ll,ll>

using namespace std;

/////////////////////////////////////////////////////

enum SegType{SUM,MIN,MAX};
template<typename T>
struct SegTree{
    int num=0, bt;
    vector<T> node, lazy;
    typedef function<T(const T &, const T &)> c1t;
    typedef function<T(const T &, const int &, const int &, const int &, const int &, const T &)> c2t;
    typedef function<T(const T &, const T &)> c3t;
    c1t calc1;c2t calc2;c3t calc3;T _init;

    void init(int num,T n,c1t calc1,c2t calc2,c3t calc3){
        int i = 0, j = 1;
        this->num = num;
        this->_init = n;
        this->calc1 = calc1;
        this->calc2 = calc2;
        this->calc3 = calc3;
        for (j = 1; j < num;)
            j *= 2;
        this->bt = j - 1;
        node.resize(j * 2 - 1, n);
        lazy.resize(j * 2 - 1, 0);
    }

    void init(int num,T n,SegType st){
        if(st==SegType::MAX){
            if(std::is_same<T,int>().value)
                _init = (T)INT_MIN;
            else if(std::is_same<T,long long>().value)
                _init = (T)LLONG_MIN;
            else
                _init = (T)n;
            init(num,n,
                [](const T &a, const T &b) { return max(a, b); },
                [](const T &a, const int &x, const int &y, const int &l, const int &r, const T &n) { return a + n; },
                [](const T &a, const T &n) { return a + n; });
        }else if(st==SegType::MIN){
            if(std::is_same<T,int>().value)
                _init = (T)INT_MAX;
            else if(std::is_same<T, long long>().value)
                _init = (T)LLONG_MAX;
            else
                _init = (T)n;
            init(num,n,
                [](const T &a, const T &b) { return min(a, b); },
                [](const T &a, const int &x, const int &y, const int &l, const int &r, const T &n) { return a + n; },
                [](const T &a, const T &n) { return a + n; });
        }else if(st==SegType::SUM){
            if(std::is_same<T,int>().value)
                _init = (T)0;
            else if(std::is_same<T,long long>().value)
                _init = (T)0;
            else
                _init = (T)n;
            init(num,n,
                [](const T &a, const T &b) { return (a + b); },
                [](const T &a, const int &x, const int &y, const int &l, const int &r, const T &n) { return (a + (r - l + 1) * n); },
                [](const T &a, const T &n) { return (a + n / 2); });
        }
    }
    void addd(int x,int y,T n){
        if(x>y)
            return;
        _addd(x, y, n, 0, 0, this->bt);
    }
    void _addd(const int& x,const int& y,const T& n,int p,int l,int r){
        if (r < x || y < l)
            return;
        if(x<=l&&r<=y){
            lazy[p] = calc2(lazy[p], x, y, l, r, n);
            evall(p);
        }else{
            if(lazy[p]!=0)
                evall(p);
            _addd(x, y, n, p * 2 + 1, l, (l + r) / 2);
            _addd(x, y, n, p * 2 + 2, (l + r) / 2 + 1, r);
            node[p] = calc1(node[p * 2 + 1], node[p * 2 + 2]);
        }
    }
    inline void evall(int x){
        node[x] += lazy[x];
        if(x<bt){
            lazy[x * 2 + 1] = calc3(lazy[x * 2 + 1], lazy[x]);
            lazy[x * 2 + 2] = calc3(lazy[x * 2 + 2], lazy[x]);
        }
        lazy[x] = 0;
    }
    void sett(int x,T n){
        gett(x);
        int i = bt+x;
        node[i] = n;
        while(i!=0){
            i = (i - 1) / 2;
            node[i] = calc1(node[i * 2 + 1],node[i * 2 + 2]);
        }
    }
    inline T gett(int x){
        T ret=_init;
        _gett(x, x, 0, 0, this->bt, ret);
        return ret;
    }
    T gett(int x,int y){
        T ret=_init;
        if(x>y)
            return ret;
        _gett(x, y, 0, 0, this->bt, ret);
        return ret;
    }
    void _gett(const int& x,const int& y,int p,int l,int r,T& ret){
        if(r<x||y<l)
            return;
        if(lazy[p]!=0)
            evall(p);
        if(x<=l&&r<=y){
            ret = calc1(ret, node[p]);
            return;
        }
        _gett(x, y, p * 2 + 1, l, (l + r) / 2, ret);
        _gett(x, y, p * 2 + 2, (l + r) / 2 + 1, r, ret);
    }
};


ll N,Q;
ll C[505050];
pll LR[505050];
pll LI[505050];
ll mk[505050],mk2[505050];
ll ans[505050];
ll i, j, k;



void query(){
    ll L, R;
    scanf("%lld%lld", &L, &R);
}

int main(){
    scanf("%lld%lld", &N, &Q);
    rep(i,0,N){
        scanf("%lld", &C[i]);
    }
    rep(i,0,505000){
        mk[i] = -1;
    }
    rep(i,0,Q){
        ll l, r;
        scanf("%lld%lld", &l, &r);
        LR[i] = {l, r};
        LI[i] = {l, i};
    }
    sort(LI, LI + Q);
    reverse(LI, LI + Q);
    SegTree<ll> sg;
    sg.init(N + 8,0,SegType::SUM);


    for (i = N-1;i>=0; --i)
    {
        if(mk[C[i]]==-1){
            mk[C[i]] = i + 1;
        }else{
            ll p = mk[C[i]];
            sg.addd(p, p, 1);
            mk[C[i]] = i + 1;
        }
        //printf("\n%lld:\n", i);
        while(j<Q&&LI[j].first==i+1){
            ll ii = LI[j].second;

            //printf("%lld,%lld,%lld\n", j, LR[ii].first, LR[ii].second);
            ans[ii] = LR[ii].second - LR[ii].first + 1;
            ans[ii] -= sg.gett(LR[ii].first, LR[ii].second);
            ++j;
        }
    }

    rep(i,0,Q){
        printf("%lld\n", ans[i]);
    }
    return 0;
}

Measured memory_bytes: 47528