#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <string>
#include <utility>
#include <algorithm>
#include <cstdio>
#include <iomanip>
#include <queue>
#include <deque>
#include <stack>
#include <fstream>
#include <cmath>
#include <random>
#include <complex>
#include <functional>
#include <bitset>
#include <sstream>
#include <cassert>
#include <time.h>

#define ll int64_t
#define Rep(i, n) for (ll i = 0; i < n; i++)
using namespace std;
typedef vector<ll> vec;
typedef vector<vec> mat;

const ll inf = 1LL << 60;

template<class T> inline void chmin(T& a, T b) {
    if (a > b) {
        a = b;
    }
}
template<class T> inline void chmax(T& a, T b) {
    if (a < b) {
        a = b;
    }
}
void printvec (vec &v) {
    Rep (i, (ll)v.size()) {
        cout << v[i] << " \n"[i+1 == (ll)v.size()];
    }
}

template <class T>
class SegTree {
    public:
    int n;
    vector<T> data;
    T def;
    function<T(T, T)> operation;
    function<T(T, T)> update;

    T _query(int a, int b, int k, int l, int r) {
        if (r <= a or b <= l) return def;
        if (a <= l and r <= b) return data[k];
        else {
            T c1 = _query(a, b, 2*k+1, l, (l+r)/2);
            T c2 = _query(a, b, 2*k+2, (l+r)/2, r);
            return operation(c1, c2);
        }
    }

    public:
    SegTree(ll _n, T _def, function<T(T, T)> _operation, function<T(T, T)> _update) : def(_def), operation(_operation), update(_update) {
        n = 1;
        while (n <= _n) {
            n *= 2;
        }
        data = vector<T>(2*n-1, def);
    }

    void change(int i, T x) {
        i += n-1;
        data[i] = update(data[i], x);
        while (i > 0) {
            i = (i-1) / 2;
            data[i] = operation(data[i*2+1], data[i*2+2]);
        }
    }

    T query(int a, int b) {
        return _query(a, b, 0, 0, n);
    }

    T operator[] (int i) {
        return data[i+n-1];
    }
};

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll N, Q;
    cin >> N >> Q;
    vec c(N);
    Rep (i, N) {
        cin >> c[i];
        c[i]--;
    }

    vector<pair<ll, ll>> query(Q);
    map<pair<ll, ll>, vec> idx;
    Rep (i, Q) {
        ll l, r;
        cin >> l >> r;
        l--;
        query[i] = {l, r};
        idx[{l, r}].push_back(i);
    }

    sort(query.begin(), query.end(), [](pair<ll, ll> a, pair<ll, ll> b) {
        return a.second < b.second;
    });

    vec last(N, -1);

    SegTree<ll> st(N, 0, [](ll a, ll b){return a+b;}, [](ll a, ll b){return a+b;});

    vec ans(Q);
    ll rnow = 0;

    Rep (i, Q) {
        ll l = query[i].first, r = query[i].second;
        for (; rnow < r; rnow++) {
            // cout << "rnow:" << rnow << "\n";
        // printvec(last); 
        // cout << "\n";
            if (last[c[rnow]] != -1) st.change(last[c[rnow]], -1);
            last[c[rnow]] = rnow;
            st.change(rnow, 1);
        }

        // Rep (j, N) {
        //     cout << st[j] << " \n"[j+1==N];
        // }
        for (ll e : idx[{l, r}]) {
            ans[e] = st.query(l, r);
        }
        // cout << l << " " << r << " " << st.query(l, r) << "\n\n";

    }

    Rep (i, Q) {
        cout << ans[i] << "\n";
    }

}

Measured memory_bytes: 86304