#include <stack>
#include <queue>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
#include <map>
#include <set>
#include <tuple>
#include <cmath>
#include <random>
#include <algorithm>
#include <vector>
#include <iostream>
#include <fstream>
#include <chrono>
#include <numeric>

#define fio ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
#define rng mt19937_64 rnd(chrono::system_clock::now().time_since_epoch().count())

#define ri(...) i64 __VA_ARGS__; rx(__VA_ARGS__)
#define rc(...) char __VA_ARGS__; rx(__VA_ARGS__)
#define rs(...) string __VA_ARGS__; rx(__VA_ARGS__)
#define rvi(x, n) vi x(n); cin >> x
#define rvvi(x, n, m) vvi x(n, vi(m)); cin >> x

#ifndef ONLINE_JUDGE
#define dbg(...) cerr << '[' << #__VA_ARGS__ << "]: "; dbg_log(__VA_ARGS__)
#else
#define dbg(...) ;;
#endif

#define fa(i, v) for (auto &i : v)
#define fi(i, n) for (i32 i = 0; i < n; i++)
#define fp(i, n) for (i32 i = 1; i < n; i++)
#define fr(i, n) for (i32 i = n - 1; i >= 0; i--)
#define fu(i) ri(_i); fi(i, _i)

#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

using namespace std;

typedef uint32_t u32;
typedef int32_t i32;
typedef uint64_t u64;
typedef int64_t i64;
#ifdef __SIZEOF_INT128__
typedef __uint128_t u128;
typedef __int128_t i128;
#endif
typedef vector<i64> vi;
typedef vector<vi> vvi;

template<typename T>
inline istream &operator>>(istream &in, vector<T> &v) {
    fa(x, v) in >> x;
    return in;
}

template<typename T>
inline ostream &operator<<(ostream &out, const vector<T> &v) {
    fa(x, v) out << x << ' ';
    return out;
}

template<typename T>
inline void rx(T &x) {
    cin >> x;
}

template<typename T, typename... R>
inline void rx(T &x, R &... l) {
    cin >> x;
    rx(l...);
}

template<typename T>
inline void dbg_log(const T &x) {
    cerr << x << '\n';
}

template<typename T, typename... R>
inline void dbg_log(const T &x, const R &... l) {
    cerr << x << ", ";
    dbg_log(l...);
}

template<typename T>
inline void wl(const T &x) {
    cout << x << '\n';
}

template<typename T, typename... R>
inline void wl(const T &x, const R &... l) {
    cout << x << ' ';
    wl<R...>(l...);
}

template<typename T,
        T op(const T &, const T &)>
class SegTree {
public:
    SegTree(i32 size, T zero) : zero(zero) {
        n = size > 1 ? 1u << (32u - __builtin_clz(size - 1)) : 1;
        base.resize(2 * n, zero);
    }

    void set(i32 k, T v) {
        for (base[k += n] = v; k /= 2;) {
            base[k] = op(base[2 * k], base[2 * k + 1]);
        }
    }

    T get(i32 i, i32 j) {
        T ri = zero, rj = zero;
        for (i += n, j += n; i < j; i /= 2, j /= 2) {
            if (i % 2) ri = op(ri, base[i++]);
            if (j % 2) rj = op(base[--j], rj);
        }
        return op(ri, rj);
    }

private:
    i32 n;
    const T zero;
    vector<T> base;
};

inline i32 add(const i32 &i, const i32 &j) {
    return i + j;
}

int main() {
    fio;

    ri(n, m);
    rvi(c, n);

    vi p(n, -1);
    vi lx(n);
    fi(i, n) {
        lx[i] = p[c[i] - 1];
        p[c[i] - 1] = i;
    }

    vector<tuple<i32, i32, i32>> qs(m);
    fi(i, m) {
        auto&[r, l, j] = qs[i];
        rx(l, r);
        j = i;
    }
    sort(all(qs));

    SegTree<i32, add> st(n, 0);
    i32 j = 0;
    vi res(m);
    fi(i, n) {
        st.set(i, 1);
        if (lx[i] >= 0) st.set(lx[i], 0);

        while (j < m) {
            auto[r, l, k] = qs[j];
            if (r - 1 > i) break;
            res[k] = st.get(l - 1, r);
            j++;
        }
    }
    fa(x, res) wl(x);

    return 0;
}


Measured memory_bytes: 29340