#include <bits/stdc++.h>
using namespace std;
 
using ll = long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vector<int>>;
using vvvi = vector<vector<vector<int>>>;
using vl = vector<ll>;
using vvl = vector<vector<ll>>;
using vvvl = vector<vector<vector<ll>>>;
using vs = vector<string>;
using vb = vector<bool>;
#define FOR(i, m, n) for (int i = (m); i < (n); i++)
#define FORR(i, m, n) for (int i = (m); i >= (n); i--)
#define REP(i, n) FOR(i, 0, (n))
#define REPR(i, n) FORR(i, (n) - 1, 0)
#define REP1(i, n) FOR(i, 1, (n) + 1)
#define REPS(c, s) for (char c : s)
#define ALL(c) (c).begin(), (c).end()
#define SORT(c) sort(ALL(c))
#define REV(c) reverse(ALL(c))
#define sz(v) (int)v.size()
#define endl '\n'
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;}
template<class T> inline void prn(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << ' ';}
template<class T> inline void printv(vector<T>& v) {int n = sz(v); if (n == 0) cout << endl; REP(i, n) cout << v[i] << (i == n - 1 ? endl : ' ');}
template<class T> inline void printvv(vector<vector<T>>& v) {for (auto u : v) printv(u);}
template<class T> inline void printlnv(vector<T>& v) {int n = sz(v); REP(i, n) cout << v[i] << endl;}
const int MOD = 1000000007;
const int INF = 1000000001;
const ll LINF = 1000000001000000001LL;
 
void solve();
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout << fixed << setprecision(numeric_limits<double>::max_digits10);
    solve();
    return 0;
}

class SegmentTree {
    int n;
    vector<ll> node;

public:
    SegmentTree(vector<ll> v) {
        n = 1;
        int s = v.size();
        while (n < s) n *= 2;
        node.resize(2 * n - 1, 0);
        for (int i = 0; i < s; i++) node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--) node[i] = node[2 * i + 1] + node[2 * i + 2];
    }

    void add(int x, ll val) {
        x += (n - 1);
        node[x] += val;
        while(x > 0) {
            x = (x - 1) / 2;
            node[x] = node[2 * x + 1] + node[2 * x + 2];
        }
    }

    ll find(int a, int b, int k = 0, int l = 0, int r = -1) {
        if(r < 0) r = n;
        if(r <= a || b <= l) return 0;
        if(a <= l && r <= b) return node[k];

        ll vl = find(a, b, 2 * k + 1, l, (l + r) / 2);
        ll vr = find(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }
};

void solve() {
    int n, q;
    cin >> n >> q;
    vi c(n);
    REP(i, n) {
        cin >> c[i];
        c[i]--;
    }
    vl v(n, 0);
    SegmentTree st(v);
    vi s(n, -1);
    vector<tuple<int, int, int>> query(q);
    int l, r;
    REP(i, q) {
        cin >> l >> r;
        l--;
        r--;
        query.emplace_back(r, l, i);
    }
    SORT(query);
    int p = -1;
    vi ans(q);
    int idx;
    for (auto m : query) {
        tie(r, l, idx) = m;
        FOR(i, p + 1, r + 1) {
            if (s[c[i]] != -1) st.add(s[c[i]], -1);
            st.add(i, 1);
            s[c[i]] = i;
        }
        p = r;
        ans[idx] = st.find(l, r + 1);
    }
    printlnv(ans);
}


Measured memory_bytes: 33472