#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)n; ++i)
#define rrep(i, n) for (int i = (int)n-1; i >= 0; --i)
using namespace std;
using ll = long long;
template<typename T>
inline bool chmax(T& a, const T& b) {
    if (a < b){
        a = b;
        return true;
    }
    return false;
}
template<typename T>
inline bool chmin(T& a, const T& b) {
    if (b < a) {
        a = b;
        return true;
    }
    return false;
}
template<typename T> vector<T> make_vec(size_t n) { return vector<T>(n); }
template<typename T, typename... Args> auto make_vec(size_t n, Args... args) {
    return vector<decltype(make_vec<T>(args...))>(n, make_vec<T>(args...));
}
template<typename T, typename U, typename... V>
typename enable_if<is_same<T, U>::value>::type fill_v(U& u, const V... v) { u = U(v...); }
template<typename T, typename U, typename... V>
typename enable_if<!is_same<T, U>::value>::type fill_v(U& u, const V... v) {
    for (auto& e : u) fill_v<T>(e, v...);
}

struct bit_vector {
    using u64 = uint64_t;

    int length, block_num;
    int block_width = 64;
    vector<u64> bit;
    vector<int> block;

    bit_vector(int length) : length(length) {
        block_num = (length + 63) >> 6;
        bit.resize(block_num + 1);
        block.resize(block_num + 1);
    }

    void set(int pos) { bit[pos >> 6] |= 1ULL << (pos & 63); }

    void build() {
        for (int i = 0; i < block_num; ++i)
            block[i+1] = block[i] + __builtin_popcountll(bit[i]);
    }

    bool operator[](int pos) const { return (bit[pos >> 6] >> (pos & 63)) & 1; }

    // [0, r)
    int rank(bool x, int r) const {
        int one = block[r >> 6] + __builtin_popcountll(bit[r >> 6] & ((1ULL << (r & 63)) - 1));
        return x ? one : r - one;
    }

    // [l, r)
    int rank(bool x, int l, int r) const { return rank(x, r) - rank(x, l); }

    // min r s.t. l <= r && rank(x, l, r) == k;
    int select(bool x, int l, int k) const {
        if (k == 0) return l;
        if (rank(x, l, length) < k) return length + 1;
        int ng = l, ok = length;
        while (ok - ng > 1) {
            int mid = (ok + ng) >> 1;
            if (rank(x, l, mid) >= k) ok = mid;
            else ng = mid;
        }
        return ok;
    }
};

template<typename T>
struct wavelet_matrix {
    int maxlog, length;
    vector<bit_vector> matrix;
    vector<int> zero_num;
    vector<int> l_pos;
    T max_value;

    wavelet_matrix(vector<T> data) : length(data.size()) {
        assert(!data.empty());
        T min_value = *min_element(data.begin(), data.end());
        max_value = *max_element(data.begin(), data.end());
        assert(0 <= min_value);
        maxlog = (max_value == 0 ? 1 : sizeof(long long int) * CHAR_BIT - __builtin_clzll(max_value + 1));
        matrix.resize(maxlog, bit_vector(length));
        zero_num.resize(maxlog);
        l_pos.resize(maxlog);

        for (int depth = 0; depth < maxlog; ++depth) {
            vector<T> zero, one;
            for (int i = 0; i < length; ++i) {
                if ((data[i] >> (maxlog - 1 - depth)) & 1) {
                    one.push_back(data[i]);
                    matrix[depth].set(i);
                } else zero.push_back(data[i]);
            }
            matrix[depth].build();
            zero_num[depth] = zero.size();
            if (depth == maxlog - 1) break;
            data = move(zero);
            data.insert(data.end(), one.begin(), one.end());
        }
    }

    T access(int i) const {
        T res = 0;
        for (int depth = 0; depth < maxlog; ++depth) {
            bool bit = matrix[depth][i];
            res = (res << 1) | bit;
            i = matrix[depth].rank(bit, i) + zero_num[depth] * bit;
        }
        return res;
    }

    int rank(T x, int l, int r) {
        for (int depth = 0; depth < maxlog; ++depth) {
            l_pos[depth] = l;
            bool bit = (x >> (maxlog - 1 - depth)) & 1;
            l = matrix[depth].rank(bit, l) + zero_num[depth] * bit;
            r = matrix[depth].rank(bit, r) + zero_num[depth] * bit;
        }
        return r - l;
    }

    int select(T x, int k) {
        if (k == 0) return 0;
        if (rank(x, 0, length) < k) return length + 1;
        for (int depth = maxlog - 1; depth >= 0; --depth) {
            bool bit = (x >> (maxlog - 1 - depth)) & 1;
            k = matrix[depth].select(bit, l_pos[depth], k);
            k -= l_pos[depth];
        }
        return k;
    }

    int select(T x, int l, int k) {
        if (k == 0) return l;
        return select(x, k + rank(x, 0, l));
    }

    // k-th number in [l, r)
    // k : 0-indexed
    T quantile(int k, int l, int r) const {
        assert(0 <= k && k < r - l);
        T res = 0;
        for (int depth = 0; depth < maxlog; ++depth) {
            int zero = matrix[depth].rank(0, l, r);
            bool bit = k >= zero;
            l = matrix[depth].rank(bit, l) + zero_num[depth] * bit;
            r = matrix[depth].rank(bit, r) + zero_num[depth] * bit;
            res = (res << 1) | bit;
            k -= zero * bit;
        }
        return res;
    }

    tuple<int, int, int> count_3way(T x, int l, int r) const {
        int lt = 0, eq = r - l, gt = 0;
        for (int depth = 0; depth < maxlog; ++depth) {
            int tmp = r - l;
            bool bit = (x >> (maxlog - 1 - depth)) & 1;
            l = matrix[depth].rank(bit, l) + zero_num[depth] * bit;
            r = matrix[depth].rank(bit, r) + zero_num[depth] * bit;
            int d = tmp - (r - l);
            eq -= d;
            (bit ? lt : gt) += d;
        }
        return forward_as_tuple(lt, eq, gt);
    }

    // [xl, xr) * [yl, yu)
    int count(int xl, int xr, T yl, T yu) const {
        yu = min(yu, max_value + 1);
        int lt_yu, lt_yl;
        tie(lt_yu, ignore, ignore) = count_3way(yu, xl, xr);
        tie(lt_yl, ignore, ignore) = count_3way(yl, xl, xr);
        return lt_yu - lt_yl;
    }
};

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

    int n, q;
    cin >> n >> q;
    vector<int> a(n), b(n), nxt(n+1, n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = n-1; i >= 0; --i) {
        b[i] = nxt[a[i]];
        nxt[a[i]] = i;
    }
    wavelet_matrix wm(b);

    while (q--) {
        int l, r;
        cin >> l >> r;
        l--;
        cout << wm.count(l, r, r, n+1) << '\n';
    }
}


Measured memory_bytes: 18508