#include <bits/stdc++.h>
using namespace std;
using pint = pair<int, int>;
using ll = long long;
using ull = unsigned long long;
using vll = vector<long long>;
using pll = pair<ll, ll>;
#define FOR(i, begin, end) \
    for (int i = (begin), i##_end_ = (end); i < i##_end_; i++)
#define IFOR(i, begin, end) \
    for (int i = (end)-1, i##_begin_ = (begin); i >= i##_begin_; i--)
#define REP(i, n) FOR(i, 0, n)
#define IREP(i, n) IFOR(i, 0, n)
#define VREP(s, ite) for (auto ite = s.begin(); ite != s.end(); ++ite)
#define FI first
#define SE second
#define ALL(v) v.begin(), v.end()
#define endl "\n"
#define ciosup  \
    cin.tie(0); \
    ios::sync_with_stdio(false);
#define eb emplace_back
#define vint vector<int>
constexpr ll INF = 1e15 + 7LL;
/* constexpr ll MOD = ll(1e9) + 7LL; */
constexpr ll MOD = 998244353LL;

template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
    for (int i = 0; i < v.size(); ++i) {
        is >> v[i];
    }
    return is;
}
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
    if (v.size() == 0) return os;
    for (int i = 0; i < v.size() - 1; ++i) {
        os << v[i] << " ";
    }
    os << v[v.size() - 1];
    return os;
}

struct Segtree {
    vector<int> data;
    int sz;
    
    Segtree(vector<int>& a) {
        int n = a.size();
        sz = 1;
        while (sz < n) {
            sz *= 2;
        }
        sz *= 2;
        data.resize(sz, 0);
        REP(i, n) {
            update(i, a[i]);
        }
    }

    int getval(int left, int right) {
        return getval_dfs(left, right, 0, sz/2, 0);
    }

    void update(int n, int val) {
        n += sz/2 - 1;
        while (true) {
            data[n] += val;
            if (n == 0) break;
            n = paridx(n);
        }
    }

    private:
    int paridx(int n) {
        return (n - 1) / 2;
    }
    int leftidx(int n) {
        return n*2 + 1;
    }
    int rightidx(int n) {
        return n*2 + 2;
    }
    int getval_dfs(int left, int right, int lbd, int rbd, int nownode) {
        if (right <= lbd) return 0;
        if (rbd <= left) return 0;
        if (left <= lbd && rbd <= right) {
            return data[nownode];
        } else {
            int vl = getval_dfs(left, right, lbd, (lbd + rbd) / 2, leftidx(nownode));
            int vr = getval_dfs(left, right, (lbd + rbd) / 2, rbd, rightidx(nownode));
            return vl + vr;
        }
    }

};

void solve() {
    ll n, q;
    cin >> n >> q;
    vll c(n);
    cin >> c;
    vector<pair<pll, int>> rl(q);
    REP(i,q){
        ll l,r;
        cin >> l >> r;
        --l;--r;
        rl[i] = make_pair(make_pair(r,l), i);
    }
    sort(ALL(rl));
    ll initr = rl[0].first.first;
    unordered_map<ll, ll> ma;
    REP(i, initr+1) {
        ma[c[i]] = i;
    }
    vint a(n, 0);
    for (auto elem: ma) {
        a[elem.second]++;
    }
    vint ans(q, 0);
    Segtree st(a);
    ll prevr = initr;
    REP(i, q) {
        ll nowr = rl[i].first.first, nowl = rl[i].first.second;
        while (nowr != prevr){
            ++prevr;
            if (ma.find(c[prevr]) != ma.end()) {
                a[ma[c[prevr]]]--;
                st.update(ma[c[prevr]], -1);
                ma[c[prevr]] = prevr;
                a[ma[c[prevr]]]++;
                st.update(ma[c[prevr]], +1);
            } else {
                ma[c[prevr]] = prevr;
                a[ma[c[prevr]]]++;
                st.update(ma[c[prevr]], +1);
            }
        }
        ans[rl[i].second] = st.getval(nowl, nowr + 1);
    }
    REP(i,q) {
        cout << ans[i] << endl;
    }
}

int main() {
    char tmp;
    while (cin >> tmp) {
        cin.putback(tmp);
        solve();
    }
}


Measured memory_bytes: 47092