#include <bits/stdc++.h>
using namespace std;

#define rep(i, m, n) for(int(i) = (int)(m); i < (int)(n); ++i)
#define rep2(i, m, n) for(int(i) = (int)(n)-1; i >= (int)(m); --i)
#define REP(i, n) rep(i, 0, n)
#define REP2(i, n) rep2(i, 0, n)
#define all(hoge) (hoge).begin(), (hoge).end()
#define en '\n'
using ll = long long;
using ull = unsigned long long;
template <class T>
using vec = vector<T>;
template <class T>
using vvec = vector<vec<T>>;
typedef pair<ll, ll> P;
using tp = tuple<ll, ll, ll>;
constexpr long long INF = 1LL << 60;
constexpr int INF_INT = 1 << 25;
//constexpr long long MOD = (ll)1e9 + 7;
constexpr long long MOD = 998244353LL;
using ld = long double;
static const ld pi = 3.141592653589793L;
typedef vector<ll> Array;
typedef vector<Array> Matrix;

template <class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}
template <class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

//グラフ関連
struct Edge {
    ll to, cap, rev;
    Edge(ll _to, ll _cap, ll _rev) {
        to = _to;
        cap = _cap;
        rev = _rev;
    }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void add_edge(Graph &G, ll from, ll to, ll cap, bool revFlag, ll revCap) {
    G[from].push_back(Edge(to, cap, (ll)G[to].size()));
    if(revFlag)
        G[to].push_back(Edge(from, revCap, (ll)G[from].size() - 1));
}

struct Mo {
    int width;
    vector<int> left, right, order;
    vector<bool> v;
    vector<int> c;
    vector<int> d;
    vector<int> ans;
    int num = 0;

    Mo(int N, int Q, vector<int> _c) : width((int)sqrt(N)), order(Q), v(N), d(N, 0), c(_c), ans(Q) {
        iota(begin(order), end(order), 0);
    }

    void add(int l, int r) { /* [l, r) */
        left.emplace_back(l);
        right.emplace_back(r);
    }

    void add(int idx) {
        d[c[idx]]++;
        if(d[c[idx]] == 1)
            num++;
    }
    void del(int idx) {
        d[c[idx]]--;
        if(d[c[idx]] == 0)
            num--;
    }
    void rem(int idx) {
        ans[idx] = num;
    }

    void run() {
        assert(left.size() == order.size());
      
        sort(begin(order), end(order), [&](int a, int b) {
            int ablock = left[a] / width, bblock = left[b] / width;
            if(ablock != bblock)
                return ablock < bblock;
            if(ablock & 1)
                return right[a] < right[b];
            return right[a] > right[b];
        });
        int nl = 0, nr = 0;
        auto push = [&](int idx) {
            v[idx].flip();
            if(v[idx])
                add(idx);
            else
                del(idx);
        };
        for(auto idx : order) {
            while(nl > left[idx])
                push(--nl);
            while(nr < right[idx])
                push(nr++);
            while(nl < left[idx])
                push(nl++);
            while(nr > right[idx])
                push(--nr);
            rem(idx);
        }
    }
};

void solve() {
    ll n, q;
    cin >> n >> q;
    vector<int> c(n);
    REP(i, n) {
        cin >> c[i];
    }

    Mo mo(n, q, c);

    REP(i, q) {
        ll l, r;
        cin >> l >> r;
        l--;
        mo.add(l, r);
    }
    mo.run();

    for(auto i : mo.ans) {
        cout << i << en;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*
    ll t;
    cin >> t;
    while(t--)*/
    solve();

    return 0;
}


Measured memory_bytes: 18904