#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int INF = 1e9;
const ll LINF = 1e18;
inline ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; }
inline ll lcm(ll a, ll b) { return a / gcd(a, b)*b; }
template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }
template<class T> ostream& operator << (ostream& out,const vector<T>& V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }
template<class T> ostream& operator << (ostream& out,const vector<vector<T> >& Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }
template<class S,class T> ostream& operator << (ostream& out,const map<S,T>& mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V> typename enable_if<is_class<T>::value==0>::type fill_v(T &t,const V &v){t=v;}
template<typename T,typename V> typename enable_if<is_class<T>::value!=0>::type fill_v(T &t,const V &v){for(auto &e:t) fill_v(e,v);}
/*
 <url:>
 問題文============================================================
 =================================================================
 解説=============================================================
 ================================================================
 */

/*
 BIT 1-index
 add : x に valを加算
 sum : [1,x] の総和を出力
 */
struct BIT {
    ll N;
    vector<ll> bit;
    BIT(ll N):N(N) {
        /* BITは[1..N]で扱う */
        bit.resize(N + 1, 0);
    }

    void add(int x, ll val){
        while (x <= N) {
            bit[x] += val;
            x += x & -x;
        }
    }

    ll sum(int x){
        ll ret = 0;
        if(x == 0) return ret;
        while (x) {
            ret += bit[x];
            x &= (x - 1);
        }
        return (ret);
    }
    // [l,r]
    ll sum(int l,int r){
        return sum(r) - sum(l-1);
    }
};

template<class Type>
Type solve(Type res = Type()){
    int N,Q; cin >> N >> Q;
    vector<ll> c(N+1);
    for(int i = 1; i <= N;i++){
        cin >> c[i];
    }
    vector<pll> Qs(Q);
    for(int i = 0; i < Q;i++){
        cin >> Qs[i].first >> Qs[i].second;
        // Qs[i].first--; Qs[i].second--;
    }

    using Item = tuple<ll,ll,ll>;
    vector<Item> qinfo(Q);
    for(int i = 0; i < Q;i++){
        qinfo[i] = Item(Qs[i].first,Qs[i].second,i);
    }
    sort(qinfo.begin(),qinfo.end(),[](const Item& l,const Item& r){
        if(get<1>(l) == get<1>(r)){
            return get<0>(l) < get<0>(r);
        }else{
            return get<1>(l) < get<1>(r);
        }
    });
    vector<int> lastAppeared(N+1,-1);

    vector<int> used(N+1,0);
    for(int i = N; i >= 1; i--){
        if(used[c[i]]) continue;
        lastAppeared[c[i]] = i;
        used[c[i]] = true;
    }
    BIT bit(N+10);
    for(int i = 1; i <= N;i++){
        if(used[i] == -1) continue;
        if(lastAppeared[i] == -1) continue;
        bit.add(lastAppeared[i],1);
    }

    // cout << c << endl;
    vector<ll> ans(Q);
    int rlast = 0;
    for(auto q:qinfo){
        int l,r,id; tie(l,r,id) = q;
        
        while(rlast < r){
            rlast++;
            int prev = lastAppeared[c[rlast]];
            lastAppeared[c[rlast]] = rlast;
            int v = lastAppeared[c[rlast]];

            // cout << c[rlast] << endl;
            // cout << rlast << " " << prev << " " << v << endl;
            bit.add(prev,-1);
            bit.add(v,1);
        }

//        if(rlast < r){
//            int prev = lastAppeared[c[r]];
//            lastAppeared[c[r]] = r;
//            int v = lastAppeared[c[r]];
//
//            bit.add(prev,-1);
//            bit.add(v,1);
//
//            rlast = r;
//        }

        ans[id] = bit.sum(l,r);
    }

    for(int i = 0; i < Q;i++){
        cout << ans[i] << endl;
    }
    return res;
}
int main(void) {
    cin.tie(0); ios_base::sync_with_stdio(false);
    solve(0);
    //cout << fixed << setprecision(15) << solve<ll>() << endl;
    return 0;
}


Measured memory_bytes: 38952