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

#define ll long long 

struct segtree {
    int size;
    vector<int> values;

    const int NEUTRAL_ELEMENT = 0;

    int merge(int a, int b) {
        return a + b;
    }

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        values.assign(size*2, NEUTRAL_ELEMENT);
    }

    void update(int i, int v) {
        update(i, v, 0, 0, size);
    }

    void update(int i, int v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            values[x] = v;
            return;
        }
        int m = lx + (rx - lx)/2;
        if (i < m) {
            update(i, v, 2*x+1, lx, m);
        } else {
            update(i, v, 2*x+2, m, rx);
        }
        values[x] = merge(values[2*x+1], values[2*x+2]);
    }

    int sum_query(int l, int r) {
        return sum_query(l, r, 0, 0, size);
    }

    int sum_query(int l, int r, int x, int lx, int rx) {
        if (lx >= l and rx <= r) return values[x];
        if (lx >= r or rx <= l) return NEUTRAL_ELEMENT;
        int m = lx + (rx - lx)/2;
        int s1 = sum_query(l, r, 2*x+1, lx, m);
        int s2 = sum_query(l, r, 2*x+2, m, rx);
        return merge(s1, s2);
    }


};

int main() {
    ios::sync_with_stdio(0); 

    int n; cin >> n;
    int q; cin >> q;
    vector<int> xs(n);
    for (int i = 0; i < n; i++) {
        cin >> xs[i];
    }

    vector<tuple<int, int, int>> queries;
    for (int query = 0; query < q; query++) {
        int l, r;
        cin >> l >> r;
        queries.emplace_back(query, --l, --r);
    }

    sort(queries.begin(), queries.end(), [] (tuple<int, int, int>& a, tuple<int, int, int>& b) 
                                                { auto [x, xx, r1] = a;
                                                  auto [y, yy, r2] = b;
                                                  return r1 < r2;});
                

    vector<pair<int, int>> queries_with_r[n];
    for (auto [id, l, r] : queries) {
        //cout << "query " << id << " " << l << " " << r << endl;
        queries_with_r[r].emplace_back(id, l);
    }


    //for (int r = 0; r < n; r++) {
        ////cout << "queries with r: " << r << endl;
        //for (auto [id, l] : queries_with_r[r])
            ////cout << "id: " << id << " left:" << l << endl;
    //}

    segtree st;
    st.init(n);

    vector<pair<int, int>> ans; // id is first
    vector<int> last_seen(n+1, -1);
    for (int r = 0; r < n; r++) {
        //cout << "number: " << xs[r] << endl;
        auto last = last_seen[xs[r]];
        //cout << "last seen at: " << last << endl;
        if (last != -1) {
            st.update(last, 0);
        }
        st.update(r, 1);
        //cout << "updated this number: " << endl;
        //cout << st.sum_query(r, r+1) << endl;;
        last_seen[xs[r]] = r;
        for (auto [id, l] : queries_with_r[r]) {
            //cout << "answering query: " << id << endl;
            //cout << l << " " << r << endl;
            ans.emplace_back(id, st.sum_query(l, r+1));
            //cout << st.sum_query(l, r+1) << endl;
        }
    }

    sort(ans.begin(), ans.end());

    for (auto x : ans) {
        cout << x.second << endl;
    }




    // segtree with where the number appeared last


    return 0; 
}



Measured memory_bytes: 47328